# A pretty puzzle

I heard it from @benjamin_leis, and he says he heard it from @CMonMattTHINK, and I love it:

The number of integer solutions to $x^2 + xy + y^2 = a$ appears to be a multiple of six for all $a \in \mathbb{Z_+}$ . Why?

How good a puzzle is this? I started my swimming class on Thursday and decided to swim non-stop until I solved it. Forty lengths later they kicked me out of the pool.

As always, spoilers below the line.

This is a very pretty puzzle. Some observations to start with:

- The curve describes an ellipse
- There are two lines of symmetry to the ellipse, $x=y$ and $x=-y$.
- The extreme points of the ellipse are on the lines $x+2y=0$ and $2x+y=0$.

### How I did it

I think it’s useful to break my solution into two bits, and acknowledge that the “correct”, underlying answer came after a lot of head-scratching and missteps. The key bit of reasoning was:

If $(X,Y)$ is an integer solution, fixing $y=Y$ gives a quadratic $x^2 + Yx + Y^2-a=0$. > I could solve that explicitly, but I don’t need to; $Y^2-a$ is an integer, so the second solution is also an integer; the solutions sum to $-Y$, so the other solution is $x=-X-Y$, which (for convenience) I’ll call $Z$.

That means, if $(X,Y)$ is an integer solution, so is $(Z,Y)$. Applying similar reasoning to the resulting point, fixing $x=Z$ gives a solution at $(Z,X)$.

We can carry on around to get $(Y,X)$, $(Y,Z)$ and $(X,Z)$ before returning to $(X,Y)$, giving six algebraically distinct solutions.

BUT! Rotational symmetry also gives a solution at $(-X, -Y)$ - so changing the signs on all of the points we found before gives a further six solutions, a total of 12.

However, they aren’t all necessarily distinct! If any pair of $X$, $Y$ and $Z$ are equal, then each point we’ve found appears twice, leaving us with six solutions (in fact, two lie on the minor axis and the remaining four at the extreme points).

### Underlying group structure

I wasn’t *happy* with my answer until I managed to shoehorn a group structure onto the solutions. The points can be classified by three pieces of information:

- Which letter is missing (isomorphic to $\mathbb{Z}_3$, with $X \sim 0$, $Y \sim 1$ and $Z \sim 2$)
- Whether the signs are + or - (isomorphic to $\mathbb{Z}_2$)
- Whether the second letter immediately follows the first (isomorphic to $\mathbb{Z}_2$ as well). By convention, $Y$ follows $X$, $Z$ follows $Y$ and $X$ follows $Z$ in a pleasing cycle.

And this gives a natural way to combine any pair of integer solutions!

The point $(X,Z)$ has $Y$ missing, positive signs and is out of order.

The point $(-Y,-X)$ has letter $Z$, negative signs and is out of order.

Combining them together, $Y + Z \sim (1 + 2)$, which is $0 \sim X$; the sign is negative, and the letters must be in order, giving $(-Y, -Z)$.

This is a group, because it’s isomorphic to $\mathbb{Z}_3 \times \mathbb{Z}_2 \times \mathbb{Z}_2$, and has order 12.

(In the degenerate case when a pair of variables is equal, each point coincides with exactly one other.)

### Even more underlying

After reading around a bit on Diophanitine equations - by which I mean scanning a few paragraphs in a huff - I realised that the ellipse equation can be rewritten as:

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

Or, equivalently, $x^2 + (-x-y)^2 + y^2 = 2a$. Why that way?

To tell the truth, that’s still a bit nebulous. However, it has the lovely pair of properties:

- by symmetry, if $(X,Y)$ is a solution, any permutation of two elements of ${ X, Y, -X-Y }$ is also a solution
- by a different symmetry, if $(X,Y)$ is a solution, any permutation of two elements of ${-X, -Y, X+Y}$ is also a solution.

If $X$, $Y$ and $-X-Y$ are all different, then there are six solutions from the first set and six from the second; if two are the same, then there are three from each.

In either case, the number of solutions is a multiple of six.

Can I stop swimming now? I need to put my computer in rice.