document.write (document.title)

 Math Help > Math Puzzles > Unsolved Problems > Unsolved 36

Unsolved Problem 36: prove nn+1 is not prime when n > 4

It seemed that this problem was solved, as the following flawed "proof" (from the now-defunct web page www.spiritual-coder.com/primepowers/) was offered.  Though it narrows down the possible values of n considerably, it doesn't prove every case.  In particular, it is not known whether there are more than five Fermat primes.

Theorem

nn+1 is never a prime number if n > 4.

Preliminary remark

All variables used below are positive integers.
n is always assumed to be greater than 4 unless indicated otherwise.

Proof

Case I: n is not a power of 2

If n is not a power of 2, it can always be written as (2m+1)p, where m and p are positive integers.

Then nn+1 = (((2m+1)p)p)(2m+1)+1

which is a multiple of ((2m+1)p)p+1

because of this factorization: x(2n+1)+1 = (x+1)(x2n - x2n-1 + ... + x2 - x + 1)

Case II: n is a power of 2

Then nn+1 = (2p)(2^p)+1 = 2(p 2^p)+1

Case IIa: p is not a power of 2

If p is not a power of 2, it can always be written as (2k+1)t, where k and t are positive integers.  Then, as in Case I, above, there is one plus a number raised to an odd power, which can be factorized:

nn+1 = (2(t2^p))(2k+1)+1

which is a multiple of 2(t2^p)+1

Case IIb: p is a power of 2

p is a power of 2, then p=2q.

Rewriting nn+1=(2p)(2^p)+1 results in the expression 2(2^(q+2^q))+1

Putting r=q+2q we recognize the expression as the Fermat number Fr.

For q=0 we have F1 = 5 and n=2, thus nn+1=5 which is prime.

For q=1 we have F3 = 257 and n=4, thus nn+1=257 which is prime.

For q > 1 we have Fermat numbers Fr with r = 6, 11, 20, 37, ... which all have a divisor of the form 2(r+1)L+1 with L integer (proven by Lucas in 1878 - see Mathworld: Fermat Number).

Alas, it is not known whether 2(r+1)L+1 is the only factor of some Fermat number thus making it prime.

Originally, the proof concluded that also in the case IIb nn+1=2(2^(q+2^q))+1 is not a prime for q > 1.

Final conclusion:

It has been shown in all but a small (but infinite) number of cases that nn+1 for n > 4 is never a prime.

The original "proof", upon which this page is based, is copyright Bernard Jacobs � 16 March 2004, and used here with attribution under the "fair use" exception to copyright law.

Internet references

Mathworld: Fermat Number.

Related pages in this website

(none)

The webmaster and author of this Math Help site is Graeme McRae.