Find all $n$ for which $n^8 + n + 1$ is prime

Find all $n$ for which $n^8 + n + 1$ is prime. I can do this by writing it as a linear product, but it took me a lot of time. Is there any other way to solve this? The answer is $n = 1$.

2 Answers

HINT:

If $w$ is a complex cube root of unity and $f(x)=x^8+x+1$

$f(w)=(w^3)^2\cdot w^2+w+1=0$

So $(x^2+x+1)|(x^8+x+1)$

• The $w$ appears only where it is defined. I assume there is a typo somewhere.
– quid
Dec 21, 2015 at 16:09
• @quid, Agreed & rectified Dec 21, 2015 at 16:11
• Not completely. I finished it. ;-)
– quid
Dec 21, 2015 at 16:13
• Note that writing $(x-1)f(x)=x^9-1-x^8+x^2=(x^3-1)(x^6+x^3+1)-x^2(x^3-1)(x^3+1)$ gives $f(x)=(x^2+x+1)(x^6-x^5+x^3-x^2+1)$ if you want the factorisation in full. Dec 21, 2015 at 16:21
• $+1$ This is the first I have seen factorization done this way, and I'm still unsure as to why it wors. Why does $f(w) = 0$ imply that $x^2 + x + 1$ is a factor? Is it somehow due to the factor theorem? Dec 21, 2015 at 16:42

Since $n^2+n+1$ divides $n^8+n+1$ and $1<n^2+n+1<n^8+n+1$ for $n>1$, then $n=1$ is the unique solution (which indeed gives a prime).