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 an + 1 is prime, then, since a > 1, it follows that an + 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,
an + 1 = ap + 1 = (a + 1)(ap-1 − ap-2 + · · · − a + 1)
and so an + 1 is not prime (each factor above is > 1).
If n > p,
an + 1 = (an/p)p + 1 = (an/p + 1)(an(p-1)/p − an(p-2)/p + · · · − an/p + 1)
which again contradicts the fact that an + 1 is prime
If you would like to see a different solution or an implementation in a different programming language Kindly let us know