Find all positive integers n for which n8+n+1 is a prime number.
Solution
Let f(x)=x8+x+1. Numerical values get large very quickly: f(1)f(2)f(3)f(4)=3=259=7×37=6565=5×13×101=65541=3×7×3121. These numbers may suggest that f(n) will be a prime number only if n=1. To prove this, we try to factorise the polynomial x8+x+1. Progress can be made if it is suspected that x2+x+1 is a factor. This can quickly be tested by using a cubic root of unity ω=1. It satisfies ω2+ω+1=0 and ω3=1, hence ω8=ω2 from which we directly see f(ω)=0. Polynomial division gives now easily the factorisation f(x)=(x2+x+1)(x6−x5+x3−x2+1). Another way to obtain this factorisation is the following. We write x8+x+1=x8−x2+x2+x+1 and observe x8−x2=x2(x6−1)=x2(x3+1)(x3−1)=x2(x3+1)(x−1)(x2+x+1). This gives f(x)=x8+x+1=(x2+x+1)(x2(x3+1)(x−1)+1). If n≥2, we have n2+n+1≥7 and n2(n3+1)(n−1)+1≥37, hence f(n) is not a prime number if n≥2. As f(1)=3 is a prime number, we conclude that n=1 is the only positive integer for which n8+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.