number theory - Prove that there exist integers such that the congruence does not hold

Let $n$ be a positive integer not of the form $6k \pm 1$. Prove that there exist integers $x,y$ such that $$x^n+y^n \not \equiv (x+y)^n \pmod{x^2+xy+y^2}.$$

From this question I wondered if $n = 6k \pm 1$ was the set of all values of $n$ for which the congruence was always true. To prove the result, it suffices to find a counterexample. Take for example $x = y = m$. Then $$x^n+y^n = 2m^n \not \equiv 2^n m^n \pmod{3m^2}.$$ Thus $m^n(2^{n-1}-1) \not \equiv 0 \pmod{3m^2}$. If $n$ is even then just pick $m$ to be an integer not divisible by $3$. I didn't see how to deal with the other case where $n$ is odd, i.e. $n = 6k+3$, since then my counterexample doesn't work.

Answer

This follows from the following lemma:

Lemma. Let $f(X), g(X) \in \mathbf Z[X]$ be two monic polynomials such that $g(a)$ divides $f(a)$ for every $a \in \mathbf Z$. Then, $g(X)$ divides $f(X)$ in the ring $\mathbf Z[X]$, i.e there is a polynomial $h(X) \in \mathbf Z[X]$ such that $f(X) = g(X) h(X)$.

Proof. If $g(a)$ divides $f(a)$ for every integer $a$, then in particular, we have that $g(a) \leq f(a)$ for every sufficiently large integer $a$. It follows that $\deg g \leq \deg f$. Thus, we may do Euclidean division (since $g$ is monic) to write

$$f(X) = g(X) q(X) + r(X)$$

where $\deg r < \deg g$. Assume that $r(X) \neq 0$. Then, by the inequality of degrees, there is some sufficiently large $N$ such that $g(N) > r(N) > 0$. Substituting $X = N$ then yields that $g(N)$ divides $r(N)$, which is impossible by the above inequalities. It follows that $r(X) = 0$. QED.

Now, consider the polynomial $(X+1)^p - X^p - 1$ ($p$ is not assumed to be prime). We will show that this polynomial is not divisible by $X^2 + X + 1$ when $p$ is not $\pm 1$ modulo $6$. Indeed, if $\zeta$ is a primitive third root of unity, i.e a root of $X^2 + X + 1$ in $\mathbb C$, then divisibility would entail that $(\zeta+1)^p = \zeta^p + 1$. However, we have

$$(\zeta+1)^p = (-\zeta^{-1})^p = (-1)^p \zeta^{-p}$$

If $p \equiv 3 \pmod{6}$, then this is equal to $-1$, and we have $-1 \neq 2$, so the equality fails. Therefore, $(X+1)^p - X^p - 1$ is not divisible by $X^2 + X + 1$ if $p \equiv 3 \pmod{6}$. By the above lemma, then, there is a particular integer $X = a$ witnessing this failure, i.e there is an integer $a$ such that $(a+1)^p - a^p - 1$ is not divisible by $a^2 + a + 1$. Then, in the original question, pick $x = a$ and $y = 1$ for a counterexample.