**Unsolved Problem 36: prove n**^{n}+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

n^{n}+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 n^{n}+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)(x^{2n} - x^{2n-1} +
... + x^{2} - x + 1)

**Case II: ****
n is**** a power of 2**

Then n^{n}+1 =
(2^{p})^{(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:

n^{n}+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=2^{q}.

Rewriting n^{n}+1=(2^{p})^{(2^p)}+1
results in the expression 2^{(2^(q+2^q))}+1

Putting r=q+2^{q}
we recognize the expression as the Fermat number F_{r}.

For q=0 we have F_{1}
= 5 and n=2, thus n^{n}+1=5 which is prime.

For q=1 we have F_{3}
= 257 and n=4, thus n^{n}+1=257 which is prime.

For q > 1 we have Fermat
numbers F_{r} 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 n^{n}+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 n^{n}+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.