# Show that $a^k + 1$ is not always prime when $k$ is a power of $2$

Let $a, k \geq 2$.

If $a^k + 1$ is a prime, conclude that $k$ is a power of $2$. Show that the converse is not true.

The hint is: if $n$ is odd, then $x^n + 1$ has a factor of $x + 1$. Please help, I don't know how to solve this.

• You should assume $a>1$, because $1^3+1$ is prime but $3$ is no power of $2$. Commented Sep 15, 2015 at 13:00

If $k$ is odd then you have the factorization $$a^k+1=(a+1)(a^{k-1}-a^{k-2}+a^{k-3}-....-a+1)$$ So $a^k+1$ can not be prime. For the converse take for example $k=2,\,a=5$ or just any odd number $a$ and $k=2^l$ for some $l\ge 1$
• This shows that $k$ is even. Does it show that $k$ is a power of $2$? Commented Sep 15, 2015 at 13:13
If $k$ is not a power of $2$,, it can be written as $\;2^l(2m+1)$, hence $$a^{2^l(2m+1)}+1=\bigl(a^{2^{\scriptstyle l}}\bigl)^{2m+1}+1=\bigl(a^{2^{\scriptstyle l}}+1\bigr)\bigl(a^{2^{\scriptstyle l}2m}-a^{2^{\scriptstyle l}(2m-1)}+\dots-a^{2^{\scriptstyle l}}+1\bigr).$$