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.