# prove that if $a^n+1$ is prime then $a$ is even and $n=2^k$ [duplicate]

This question already has an answer here:

i managed to show that $a$ is a even (suppose it is, and then show that $2|a^n+1$) for the second part, I understand it has something to do with fermat numbers but couldn't solve. please help

## marked as duplicate by user147263, Jonas Meyer, Daniel, J. W. Perry, Mike PierceJun 9 '15 at 5:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• $a=1$ gives $a^n+1$ prime, but $a$ is not even. – user26486 Jun 5 '15 at 16:28

## 2 Answers

For fun, we reword the very good hint of Antoine using the language of congruences. Suppose that $a\gt 1$, and $n=2^km$, where $m\gt 1$ is odd.

Then $a^{(2^k)}\equiv -1 \pmod{a^{(2^k)}+1}$, and therefore $$a^n=(a^{(2^k)})^m \equiv -1\pmod{a^{(2^k)}+1}.$$

Hint. Suppose $n = 2^k m$, where $m\neq 1$ is an odd number. Then $$a^n + 1 = \left(a^{2^k}\right)^m + 1^m\text{.}$$