5
$\begingroup$

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$?

  • 0
    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.2011-03-22

2 Answers 2

7

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\,.$

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

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

3

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.