# If $a^n + 1$ is prime for some numbers $a \geq 2$ and $n\geq 1$, show that n must be a power of 2

If $a^n + 1$ is prime for some numbers $a \geq 2$ and $n\geq 1$, show that n must be a power of 2.

I understand how to do this proof. Specifically by showing that $x^n + 1$ is composite. My question is how to come up with the notion to show that $(x+1)$ divides $x^n + 1$. My prof used a hand wavy argument stating that because $x^m + 1$ equals 0 when $x = -1$ But that does not comvince me in the slightest. I am not seeing how that implies divisibility.

• $x+1$ doesn't always divide $x^n+1$, but that is not necessary here. See my answer. – TonyK Feb 24 '16 at 18:32

Your teacher was probably trying to quickly show that:
$x^{2n+1} + 1 = (x+1)(x^{2n}-x^{2n-1}+x^{2n-2}- ... +x^2-x+1)$

The signs there in the RHS are alternating i.e. $+,-,+,-,$ etc.

Note that this formula is true only if $m=2n+1$ is odd.

In general, note that if a polynomial (like e.g. $x^{2n+1}+1$) has a root $a$, then that polynomial is divisible by $(x-a)$. Since $x^{2n+1}+1$ obviously has a root $-1$, it means it's divisible by $(x+1)$.

• The statement is true for even $n$ too, as long as $n$ is not a power of $2$. – TonyK Feb 24 '16 at 18:38
• @TonyK I was talking about the polynomial formula only. – peter.petrov Feb 24 '16 at 18:40
• You were trying (unsuccessfully) to read the teacher's mind. This is a perfectly valid exercise, and you missed the point of it. – TonyK Feb 24 '16 at 18:57

Since (-1)^m + 1 = 0 when m is odd, we have that -1 is a root of $x^m + 1$ for m odd. Therefore $x - (-1) = x + 1$ divides $x^m + 1$ since x^m + 1 is the product of linear factors of its roots.

Polynomial division with remainder is always possible. That is, we can certainly find polynomials $q(x)$, $r(x)$ such that $x^n+1=q(x)\cdot (x+1)+r(x)$ and $\deg r<\deg(x+1)$. The latter condition makes $r$ constant and the value of that constant can be found by evaluating at $x=-1$.

• So $r=0$ if $n$ is odd, and $r=2$ if $n$ is even... – TonyK Feb 24 '16 at 18:32

$x+1$ doesn't necessarily divide $x^n+1$ (for instance, $2+1$ doesn't divide $2^6+1=65$). But it does if $n$ is odd and $\ge 3$, as more than one alternative answer demonstrates.

And if $n$ is not odd, but is not a power of $2$, then $n$ can be expressed as $uv$ where $u$ is an odd number $\ge 3$. And now $x^v+1$ divides $(x^v)^u+1 = x^n+1$.

In our example, we have $n=6$, so $u=3$ and $v=2$. And indeed $2^2+1$ divides $65$.