Exercise 2.8.17 (Prime divisors of $a^{2^n} + 1$)

Proof. Write $k=2^{j}l$, where $l$ is odd. Assume for contradiction that $l>1$. Then, using the identity, true for all odd $l$,

we obtain

Since $a>1$, and $l>1$, we have $1<a^{2^j}+1<a^{2^n}+1=N$. Therefore $a^{2^j}+1$ is a non trivial divisor of $a^k+1$, so $a^k+1$ is composite. This contradiction shows that $l=1$, and $k=2^j$, so that $k$ is a power of $2$.

Now assume that $p\mid a^{2^n}+1$, where $p$ is an odd prime. We must show that $p\equiv 1(\mathit{mod}{2}^{n+1})$.

Since $p\mid a^{2^n}+1$, $p$ is relatively prime to $a$, so we can consider the order $h$ of $a$ modulo $p$.

From $a^{2^n}\equiv -1(\mathit{mod}p)$, and $a^{2^{n+1}}={\left(a^{2^n}\right)}^2\equiv 1(\mathit{mod}p)$, we deduce that

Then $h=2^k$, where $n<k\le n+1$. Hence $h=2^{n+1}$.

By Fermat’s Theorem $a^{p-1}\equiv 1(\mathit{mod}p)$. Therefore $h=2^{n+1}\mid p-1$, so

□