Solving $x^2+xy+y^2 \equiv 0\pmod{n^2} $ When I was dealing with the equation  

$x^2+xy+y^2 \equiv 0 \pmod{n^2}$  

At $n$ = 3, I found that x, y must be $\equiv 0 \pmod n$. Then I wonder and did $n =$ 3 to 10k, using a mini computer program. Interestingly, I found that only when n is in this OEIS sequence, the above statement is true.
Can someone give some hints or tips on how to proof this?
In other words, how should I prove (if this is even true) that:

For all n without prime factor congruent to 1 mod 6, the equation $x^2+xy+y^2 \equiv 0 \pmod{n^2}$ has only solutions $(x, y) = (0, 0)  \pmod n$?

Thanks a lot.
 A: Claim:

If $n$ is a positive integer such that, for some integers $x,y$, not both congruent to zero, mod $n$, we have
$$x^2 + xy + y^2\equiv 0\;(\text{mod}\;n^2)$$
then $n$ has a prime factor congruent to $1$, mod $6$.

Proof:

For $n=1$, the claim holds vacuously, since the hypothesis fails (for any integers $x,y$, it's automatic that $x,y$ are both congruent to zero, mod $1$).

Thus, assume $n > 1$.

Let $n$ be the least positive integer for which a counterexample exists.

Thus, $n$ is the least positive integer such that


*

*There are integers $x,y$, not both congruent to zero, mod $n$, for which $x^2 + xy + y^2\equiv 0\;(\text{mod}\;n^2)$.$\\[4pt]$

*$n$ has no prime factor congruent to $1$, mod $6$.


Our goal is to derive a contradiction.

Let $d=\gcd(x,y,n)$.

Since $x,y$ are not both zero, $d$ is a positive integer.

Then we can write 


*
$x=dx_1$


$y=dy_1$

$n=dn_1$


where $x_1,y_1,n_1$ are integers.

Since $x,y$ are not both congruent to zero, mod $n$, we have $d < n$, hence $n_1  > 1$. 

If $d>1$, then $n_1 < n$, but then
$$x^2 + xy + y^2\equiv 0\;(\text{mod}\;n^2)$$
can be reduced to
$$x_1^2 + x_1y_1 + y_1^2\equiv 0\;(\text{mod}\;n_1^2)$$
where 


*

*$x_1,y_1$ are integers, not both congruent to zero, mod $n_1$.$\\[4pt]$

*$n_1$ has no prime factor congruent to $1$, mod $6$.


so we have a counterexample with $n_1 < n$, contradiction.

Hence, we must have $d=1$, so $\gcd(x,y,n)=1$.

If $n$ is even, then 
\begin{align*}
&x^2 + xy + y^2\equiv 0\;(\text{mod}\;n^2)\\[4pt]
\implies\;&x^2 + xy + y^2\equiv 0\;(\text{mod}\;2)\\[4pt]
\end{align*}
but then $x,y$ must both be even, contrary to $\gcd(x,y,n)=1$.

Next, let $e=\gcd(y,n)$.

Suppose $e > 1$

Since $\gcd(x,y,n)=1$, it follows that $\gcd(x,e)=1$.
\begin{align*}
\text{Then}\;\;&x^2 + xy + y^2\equiv 0\;(\text{mod}\;n^2)\\[4pt]
\implies\;&x^2 + xy + y^2\equiv 0\;(\text{mod}\;e)\\[4pt]
\implies\;&x^2\equiv 0\;(\text{mod}\;e)\\[4pt]
\end{align*}
contrary to $\gcd(x,e)=1$.

Hence, we must have $e=1$, so $\gcd(y,n)=1$.

Analogously, we get $\gcd(x,n)=1$.

Let $p$ be a prime factor of $n$.

From $\gcd(y,n)=1$, we get $\gcd(y,p)=1$.
\begin{align*}
\text{Then}\;\;&x^2 + xy + y^2\equiv 0\;(\text{mod}\;n^2)\\[4pt]
\implies\;&x^2 + xy + y^2\equiv 0\;(\text{mod}\;p)\\[4pt]
\implies\;&(x-y)(x^2 + xy + y^2)\equiv 0\;(\text{mod}\;p)\\[4pt]
\implies\;&x^3-y^3\equiv 0\;(\text{mod}\;p)\\[4pt]
\implies\;&x^3\equiv y^3\;(\text{mod}\;p)\\[4pt]
\implies\;&\bigl({\small{\frac{x}{y}}}\bigr)^3\equiv 1\;(\text{mod}\;p)\\[4pt]
\end{align*}
Thus, the order of ${\large{\frac{x}{y}}}$, mod $p$, is either $1$ or $3$.

Consider two cases . . .

Case $(1)$:$\;$The order of ${\large{\frac{x}{y}}}$, mod $p$, is $3$.

But the order of ${\large{\frac{x}{y}}}$, mod $p$, must divide $(p-1)$, hence $3{\,\mid\,}(p-1)$, so $p\equiv 1\;(\text{mod} 3)$.

Since $n$ is odd, so is $p$, hence from $p\equiv 1\;(\text{mod}\;3)$, we get $p\equiv 1\;(\text{mod}\;6)$, contradiction.

Case $(2)$:$\;$The order of ${\large{\frac{x}{y}}}$, mod $p$, is $1$.

Then from ${\large{\frac{x}{y}}}\equiv 1\;(\text{mod}\;p)$, we get $x\equiv y\;(\text{mod}\;p)$, hence
\begin{align*}
&x^2 + xy + y^2\equiv 0\;(\text{mod}\;p)\\[4pt]
\implies\;&y^2 + (y)y + y^2\equiv 0\;(\text{mod}\;p)\\[4pt]
\implies\;&3y^2\equiv 0\;(\text{mod}\;p)\\[4pt]
\implies\;&p{\,\mid\,}3y^2\\[4pt]
\implies\;&p{\,\mid\,}3\qquad\text{[since $\gcd(y,p)=1$]}\\[4pt]
\implies\;&p=3\\[4pt]
\implies\;&3{\,\mid\,}n\\[4pt]
\implies\;&9{\,\mid\,}n^2\\[4pt]
\implies\;&x^2 + xy + y^2\equiv 0\;(\text{mod}\;9)\\[4pt]
\end{align*}
Since $p=3$, then from


*

*$\gcd(x,p)=1$, and $\gcd(x,p)=1$.$\\[4pt]$

*$x\equiv y\;(\text{mod}\;p$.


we get $x\equiv 1\;(\text{mod}\;3)$, and $x\equiv 1\;(\text{mod}\;3)$.

Note that we can't have $x\equiv y\;(\text{mod}\;9)$, else
\begin{align*}
&x^2 + xy + y^2\equiv 0\;(\text{mod}\;9)\\[4pt]
\implies\;&y^2 + (y)y + y^2\equiv 0\;(\text{mod}\;9)\\[4pt]
\implies\;&3y^2\equiv 0\;(\text{mod}\;9)\\[4pt]
\implies\;&y^2\equiv 0\;(\text{mod}\;3)\\[4pt]
\end{align*}
contradiction, since $p=3$, and $\gcd(y,p)=1$.

Testing the congruence $x^2 + xy + y^2\equiv 0\;(\text{mod}\;9)$, subject to the constraints


*

*$x\equiv 1\;(\text{mod}\;3$, and $x\equiv 1\;(\text{mod}\;3$.$\\[4pt]$

*$x\not\equiv y\;(\text{mod}\;9)$.$\\[4pt]$

*$1 \le x,y \le 8$.


we find that there are no solutions, so case $(2)$ yields a contradiction.

Thus, both cases yield a contradiction, which completes the proof of the claim.
