15. Let $n$ be a positive integer not exceeding 2014 with the property that $x^{2}+x+1$ is a factor of $x^{2 n}+x^{n}+1$. Find the sum of all possible values of $n$.
(2 marks)
Let $n$ be a positive integer not exceeding 2014 with the property that $x^{2}+x+1$ is a factor of $x^{2 n}+x^{n}+1$. Find the sum of all possible values of $n$.
15. 1352737
15. Since \(x^{3}-1=(x-1)\left(x^{2}+x+1\right)\), we have \(x^{3} \equiv 1\left(\bmod x^{2}+x+1\right)\). We consider the following three cases (in what follows \(k\) is a non-negative integer):
- If \(n=3 k\), we have \(x^{2 n}+x^{n}+1=\left(x^{3}\right)^{2 k}+\left(x^{3}\right)^{k}+1 \equiv(1)^{2 k}+(1)^{k}+1=3\left(\bmod x^{2}+x+1\right)\). Hence \(x^{2}+x+1\) is not a factor of \(x^{2 n}+x^{n}+1\) in this case.
- If \(n=3 k+1\), we have \(x^{2 n}+x^{n}+1=\left(x^{3}\right)^{2 k} \cdot x^{2}+\left(x^{3}\right)^{k} \cdot x+1 \equiv(1)^{2 k} \cdot x^{2}+(1)^{k} \cdot x+1 \equiv 0(\bmod \left.x^{2}+x+1\right)\). Hence \(x^{2}+x+1\) is always a factor of \(x^{2 n}+x^{n}+1\) in this case.
- Finally, if \(n=3 k+2\), we have
\[
x^{2 n}+x^{n}+1=\left(x^{3}\right)^{2 k} \cdot x^{4}+\left(x^{3}\right)^{k} \cdot x^{2}+1 \equiv(1)^{2 k} \cdot x^{4}+(1)^{k} \cdot x^{2}+1 \equiv x^{4}+x^{2}+1\left(\bmod x^{2}+x+1\right) \text{. }
\]

According to the previous case, \(x^{4}+x^{2}+1\) is divisible by \(x^{2}+x+1\). That is, \(x^{2}+x+1\) is always a factor of \(x^{2 n}+x^{n}+1\) in this case.

It follows that the answer is
\[
(1+2+\cdots+2014)-(3+6+\cdots+2013)=\frac{(1+2014) \times 2014}{2}-\frac{(3+2013) \times 671}{2}=1352737 .
\]

Remark. We may begin by trials on small cases which show that \(1,2,4,5\) are possible values of \(n\) while 3 and 6 are not. This would easily have led us to guess the answer correctly, and
suggest that in working out a complete solution we should consider the values of \(n\) modulo 3.