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

Question

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.

Answer 1

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.