Number of integer solutions to $x^2 + xy + y^2 = c$

Inspired by this question on Mathematica StackExchange:

Consider the set of integer solutions $$x, y \in \mathbb{Z}$$ to the equation $$x^2 + xy + y^2 = m$$, for $$m \in \mathbb{N}$$. Conjecture: the number of distinct solutions to this equation is divisible by 6 for all integer $$m$$.

I have done a brute-force calculation in Mathematica for $$m \leq 10^4$$, and have not found any counterexamples. For example, there are:

• 0 integer solutions for $$m = 2$$;
• 6 distinct solutions for $$m = 3$$ [$$(x,y) = \pm (2, -1)$$, $$(x,y) = \pm (-1, 2)$$, and $$(x,y) = \pm (1, 1)$$];
• 12 distinct solutions for $$m = 7$$;
• 18 distinct solutions for $$m = 49$$;

and so forth. The largest number of solutions Mathematica found was 54 solutions, for $$m = 8281$$. All of these are divisible by 6.

Is there a counterexample to this conjecture for some larger value of $$m$$? Or can the conjecture be proven?

I suspect that a proof will involve some kind of hidden symmetry of the polynomial $$x^2 + xy + y^2$$ that maps integer solutions to integer solutions; but I haven't been able to nail it down. It's not hard to see that the number of solutions must be even (if $$(x,y)$$ is a solution, then so is $$(-x, -y)$$, and these are distinct unless $$x = y = 0$$); but the divisibility by 6 is much more mysterious to me.

• If $(x,y)$ is a solution, then as well as $(-x,-y)$, you also get $(y,x)$ and $(-y,-x)$, unless $|y|=|x|$. Aug 11 '20 at 18:25
• @TonyK: Yeah, I found that symmetry too. What's remarkable to me is that there always seem to be the "right" combination of solutions to make the total number divisible by 6. For example, when $m = 3$, there are two solutions with $|y| = |x|$ and four with $|y| \neq |x|$ (all related by the above symmetries. When $m = 13$, there are 12 solutions, all of which have $|x| \neq |y|$. Somehow, the number of four-fold symmetric solutions is always "correctly" balanced out by a two-fold symmetric solution to make the total number of solutions divisible by 6. Aug 11 '20 at 19:03

This is a slightly different approach to your problem. Let $$\omega$$ be the cube root of unity. Then $$x^2+xy+y^2=(x-\omega y)(x-\omega^2 y)=m.$$ If this has a solution, then it means there exists an element $$\alpha=x-\omega y$$ in the ring $$\Bbb{Z}[\omega]$$ such that its norm $$N(\alpha)=m$$. But if you consider the six units of the ring $$\Bbb{Z}[\omega]$$, they are $$\{\pm 1, \pm \omega, \pm \omega^2\}$$, then the norm of $$\alpha u$$, where $$u$$ is a unit is also $$m$$. So for every solution $$\alpha$$ you have six solutions namely, $$\pm\alpha, \pm\omega \alpha, \pm \omega^2 \alpha$$.

• Neat solution, and one that really shows the underlying structure. If I've done my calculations correctly, it looks like the solutions related in this way are $\pm(x,y)$, $\pm(y, -x-y)$, and $\pm(-x-y, x)$. By the method of construction, these are all automatically distinct unless $x = y = 0$. Aug 11 '20 at 23:05

Observe that,

$$(x+y)^2+(x+y)(-y)+(-y)^2=x^2+2xy+y^2-xy-y^2+y^2=x^2+xy+y^2$$

Therefore $$(x,y)$$ is a solution then so is $$(x+y,-y)$$.

We consider the following cases

Case 1

When $$x=y=k$$ then $$(k,k), (-k,-k), (2k,-k), (-2k,k), (-k,2k), (k,-2k)$$ are $$6$$ distinct solutions.

Case 2

If $$y=0$$ but $$x\neq0$$ then $$(x,0),(-x,0),(x,-x),(-x,x),(0,x),(0,-x)$$ are $$6$$ distinct solutions. This also works when $$x=-y$$.

Case 3

Otherwise, for $$|x|\neq |y|$$ and $$xy\neq 0$$, $$(x,y),(-x,-y),(y,x),(-y,-x),(x+y,-y),(x+y,-x),(-x-y,x),(-x-y,y),(-x,x+y),(-y,x+y),(x,-x-y),(y,-x-y)$$ are all $$12$$ distinct solutions.

• What if $y = 0$? Then $(x, y)$ and $(x+y,-y)$ aren't distinct solutions. Aug 11 '20 at 18:57
• I have added that case. See. Aug 11 '20 at 19:02
• @MichaelSeifert I have added all cases. Aug 11 '20 at 19:09
• nice approach (+1) Aug 11 '20 at 19:27

If $$(x,y)$$ is a solution then so are all of $$\{(x,y),(-x,-y),(y,x),(-y,-x),(-x,x+y),(x,-x-y)\}$$ which are all distinct unless $$x$$ and $$y$$ fall within a set of the form $$\{(z,z),(-z,-z),(-z,2z),(z,-2z),(2z,-z),(-2z,z)\}$$ so that we always have a multiple of $$6$$ solutions.

• Are all of the solutions in your first set necessarily distinct? For example, if $x = 0$, then $(x, y) = (-x, x+y)$ and $(-x, -y) = (x, -x-y)$. Maybe I've misunderstood your second comment? Aug 11 '20 at 18:54
• @MichaelSeifert It seems you are correct. If $x=y=0$ then $m=0\not\in\mathbb{N}$. Otherwise WLOG $y=0$ and we have distinct solutions$$\{(x,0),(-x,0),(0,x),(0,-x),(-2x,x),(2x,-x)\}$$ Aug 11 '20 at 19:09