6
$\begingroup$

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

$\endgroup$

2 Answers 2

9
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ The $w$ appears only where it is defined. I assume there is a typo somewhere. $\endgroup$
    – quid
    Dec 21, 2015 at 16:09
  • $\begingroup$ @quid, Agreed & rectified $\endgroup$ Dec 21, 2015 at 16:11
  • $\begingroup$ Not completely. I finished it. ;-) $\endgroup$
    – quid
    Dec 21, 2015 at 16:13
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 21, 2015 at 16:21
  • $\begingroup$ $+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? $\endgroup$
    – Yiyuan Lee
    Dec 21, 2015 at 16:42
4
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.