Quote:

Originally Posted by

**Nerdfighter** My teacher has given my class a challenge task: to prove the following implication:

Let $\displaystyle a $and $\displaystyle n$ be integers such that $\displaystyle n \geq 1$ and $\displaystyle a \geq 2$.

Prove: If $\displaystyle a^n + 1$ is prime, then there exists an integer $\displaystyle m$ such that $\displaystyle n = 2^m$

the following identity was given to us to use:

Let $\displaystyle b$ and $\displaystyle k$ be integers and $\displaystyle k \geq 1$, then

$\displaystyle (b^2)^k + b^1 + 1 = (b + 1)(b^2k - b^2k-1 + ... - b + 1) = (b + 1) \sum_{j=0}(-1)^jb^j$ <------ note, there should be a $\displaystyle k$ on the top of the $\displaystyle \sum$

The question is equivalent to: If $\displaystyle n$ is not a power of 2, then $\displaystyle a^n+1$ is not prime.

Let $\displaystyle n=2^mk$ for some odd integer $\displaystyle k>1.$ Then, writing $\displaystyle b=a^{2^m},$ we have

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

and $\displaystyle 1<b+1<b^k+1.$ This shows that $\displaystyle a^n+1$ is composite.