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ⁿ + 1 is prime, then, since a > 1, it follows that aⁿ + 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ⁿ + 1 = a^p + 1 = (a + 1)(a^p-1 − a^p-2 + · · · − a + 1)

and so aⁿ + 1 is not prime (each factor above is > 1).

If n > p,

aⁿ + 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ⁿ + 1 is prime