# Let a and n be positive integers with a > 1. Prove that, if a^n + 1 is prime, then a is even and n is a power of 2.

## Solution

If a^{n} + 1 is prime, then, since a > 1, it follows that a^{n} + 1 must be odd and so a must be even.

If n > 1, then if n is not a power of 2, we would have that n is divisible by some odd prime, say p.

If n = p,

a^{n} + 1 = a^{p} + 1 = (a + 1)(a^{p-1} − a^{p-2} + · · · − a + 1)

and so a^{n} + 1 is not prime (each factor above is > 1).

If n > p,

a^{n} + 1 = (a^{n/p})^{p} + 1 = (a^{n/p} + 1)(a^{n(p-1)/p} − a^{n(p-2)/p} + · · · − a^{n/p} + 1)

which again contradicts the fact that a^{n} + 1 is prime