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.