Maths Olympiad Prep

Library / /17 of 39

Algebra Difficulty 5.3 AIME, harder Prove it Ireland

Find all positive integers nn for which n8+n+1n^8 + n + 1 is a prime number.

Solution

Let f(x)=x8+x+1f(x) = x^8 + x + 1. Numerical values get large very quickly:
f(1)=3f(2)=259=7×37f(3)=6565=5×13×101f(4)=65541=3×7×3121. \begin{aligned} f(1) &= 3 \\ f(2) &= 259 = 7 \times 37 \\ f(3) &= 6565 = 5 \times 13 \times 101 \\ f(4) &= 65541 = 3 \times 7 \times 3121. \end{aligned}
These numbers may suggest that f(n)f(n) will be a prime number only if n=1n = 1. To prove this, we try to factorise the polynomial x8+x+1x^8 + x + 1. Progress can be made if it is suspected that x2+x+1x^2 + x + 1 is a factor. This can quickly be tested by using a cubic root of unity ω1\omega \neq 1. It satisfies ω2+ω+1=0\omega^2 + \omega + 1 = 0 and ω3=1\omega^3 = 1,
hence ω8=ω2\omega^8 = \omega^2 from which we directly see f(ω)=0f(\omega) = 0. Polynomial division gives now easily the factorisation f(x)=(x2+x+1)(x6x5+x3x2+1)f(x) = (x^2+x+1)(x^6-x^5+x^3-x^2+1). Another way to obtain this factorisation is the following. We write x8+x+1=x8x2+x2+x+1x^8+x+1 = x^8 - x^2 + x^2 + x + 1 and observe
x8x2=x2(x61)=x2(x3+1)(x31)=x2(x3+1)(x1)(x2+x+1). x^8 - x^2 = x^2(x^6 - 1) = x^2(x^3 + 1)(x^3 - 1) = x^2(x^3 + 1)(x - 1)(x^2 + x + 1).
This gives f(x)=x8+x+1=(x2+x+1)(x2(x3+1)(x1)+1)f(x) = x^8 + x + 1 = (x^2 + x + 1)(x^2(x^3 + 1)(x - 1) + 1). If n2n \ge 2, we have n2+n+17n^2 + n + 1 \ge 7 and n2(n3+1)(n1)+137n^2(n^3 + 1)(n - 1) + 1 \ge 37, hence f(n)f(n) is not a prime number if n2n \ge 2. As f(1)=3f(1) = 3 is a prime number, we conclude that n=1n = 1 is the only positive integer for which n8+n+1n^8 + n + 1 is a prime number.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.