Problem:
The polynomial x2n+1+(x+1)2n is not divisible by x2+x+1 if n equals
Answer Choices:
A. 17
B. 20
C. 21
D. 64
E. 65
Solution:
Let f(x)=x2+x+1. Let gn(x)=x2n+1+(x+1)2n,f(x)=(x−r)(x−r′), where
r=2−1+−3 and r′=2−1−−3
are the roots of f(x)=0. Thus f(x) divides gn(x) if and only if both x−r and x−r′ divide gn(x). That is, if gn(r)=gn(r′)=0. Since r and r′ are complex conjugates, it suffices to determine those n for which gn(r)=0.
Note that gn(x)=[x2]n+[(x+1)2]n+1. Also note that r and r+1=21+−3 are both 6th roots of 1. (It's easy to see this with Argand diagrams.) Thus r2 and (r+1)2 are both cube roots of 1. Thus the value of gn(r) depends only on the remainder when n is divided by 3. A direct computation (again easiest with Argand diagrams) shows that
g0(r)=3,g1(r)=0,g2(r)=0
Thus f(x) does not divide gn(x) if and only if n is divisible by 3.