$a^n+1$ prime $\Rightarrow n = 2^k$ is a power of $2$

Solution 1:

At the core it is the trivial identity $\rm\, (-1)^m \equiv -1\ $ for odd $\rm\,m.\,$ So if $\rm\,n\,$ has odd factor $\rm\,m,\ \ n = k m,\,$

then we have $\rm\ \ a^k\equiv -1\ \,\Rightarrow\,\ a^n =\, (a^k)^m\equiv -1\ \ (mod\ a^k+1),\ $ hence $\rm\ a^k+1\ $ divides $\rm\ a^n+1\,.$

Or $ $ put $\rm\ x = a^k\ $ in $\rm\ x+1\mid x^m + 1,\, $ by the Factor Theorem: $\rm\ x-c\, \mid\, f(x)-f(c)\ $ in $\rm\ \mathbb Z[x].$

Note the this is simply the case $\rm\,m\,$ odd, $\rm\ x\to -x\ $ in this prior question today.

Solution 2:

For some non-negative integers $b$ and $k$, we have $n=2^b(2k+1)$, in which case

$$a^n+1 = (a^{2^b}+1)(a^{2k\cdot2^b}-a^{(2k-1)2^b}+a^{(2k-2)2^b}-\cdots -a^{3\cdot2^b}+a^{2\cdot2^b}-a^{2^b}+1)$$

If $k>0$ and $a>1$ then this is a factorisation (if $a=1$ then $a^n+1$ is prime); but if $k=0$, i.e. if $n$ is a power of 2, then it leaves you where you started so it is still possible that $a^n+1$ could be prime.