factorization of a^n+1?

I'm trying to prove that $a^n+1$ can only be prime if $n$ is a power of $2$. Is there a general factorization of $a^n+1$?

-
If $n$ is prime then you have $a^n + 1 = (a + u_n^1)(a + u_n^2)\cdots(a + u_n^n)$ where $u_n$ is an $n$th root of unity. – Alex Becker Mar 22 '11 at 23:24

3 Answers

At the core it is the trivial identity $\rm\ (-1)^m \equiv -1\$ for odd $\rm\:m\:.\:$ So if $\rm\:n\:$ has odd factor $\rm\:m\:,\ \ n = k\ m\:,\:$

then we have $\rm\ \ a^k\equiv -1\ \:\Rightarrow\:\ a^n \:=\: (a^k)^m\:\equiv\: -1\ \ (mod\ a^k+1)\:,\$ hence $\rm\ a^k+1\$ divides $\rm\ a^n+1\:.$

Alternatively put $\rm\ x = a^k\$ in $\rm\ x+1\ |\ x^m + 1\:,\:$ by the Factor Theorem $\rm\ x-a\ |\ f(x)-f(a)\$ in $\rm\ \mathbb Z[x]\:.$

Note the this is simply the case $\rm\:m\:$ odd, $\rm\ x\to -x\$ in this prior question today.

-

This question has been asked at Math Forum. Here is the link.

-

For some non-negative integers $b$ and $k$, we have $n=2^b(2k+1)$, in which case

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

If $k>0$ and $a>1$ then this is a factorisation (if $a=1$ then $a^n+1$ is prime); but if $k=0$, i.e. if $n$ is a power of 2, then it leaves you where you started so it is still possible that $a^n+1$ could be prime.

-