# Number Theory Solutions: Siegel's Ellipse

#### William F. Hammond

The following problem was on the last assignment:

Can you find the smallest integer m >= 2 with the property that there are no integers x, y for which

5 x^{2} + 11 y^{2} = 1 (mod m) ?

The answer to the question is ``No'' since there is no smallest such m. In other words, even though there is obviously no integer point on the ellipse

5 x^{2} + 11 y^{2} = 1

there are, for each modulus m, points (x, y) with integer coordinates for which the congruence mod m is satisfied. In fact, the mathematician C. L. Siegel (1896-1981) produced this as an example of an ellipse that for each modulus m is ``equivalent'' to the ellipse

x^{2} + 55 y^{2} = 1 .

Proof. To show the existence of solutions (x, y) mod m for each m it is enough by the Chinese Remainder Theorem to treat the case where m is the power of a prime.

If m is the power of an odd prime, or is any positive odd number, then, letting u_{m} be a multiplicative inverse of 4 mod m one has

5 u_{m}^{2} + 11 u_{m}^{2} = 16 u_{m}^{2} = 1 (mod m) .

One then proceeds to treat the case m = 2^{n}, n >= 1 recursively. Bear in mind that the value of an integer t mod 2^{n} determines the value of t^{2} mod 2^{n+1}.

It is obvious that (x, y) is a solution mod 4 if and only if

x = 1 and y = 0 (mod 2)

since all odd squares are 1 mod 4.

However, (1, 0) is not a solution mod 8. One sees that every solution mod 8 must be congruent to ({+/-} 1, 2) mod 4, while ({+/-} 1, {+/-} 2) and ({+/-} 3, {+/-} 2) are all of the distinct solutions mod 8. Of the distinct solutions mod 8 only ({+/-} 1, {+/-} 2) are solutions mod 16, while the distinct solutions mod 16 are ({+/-} 1, {+/-} 2), ({+/-} 7, {+/-} 2), ({+/-} 1, {+/-} 6), and ({+/-} 7, {+/-} 6). These observations lead one to guess that there might be 2^{n} solutions mod 2^{n} for all n >= 1.

Suppose that (x_{n}, y_{n}) is a solution mod 2^{n} for n >= 3. Then there is an integer u_{n} such that

5 x_{n}^{2} + 11 y_{n}^{2} = 1 + 2^{n} u_{n} ,

and the validity of this relation depends only on (x_{n}, y_{n}) mod 2^{n-1}. If (x_{n+1}, y_{n+1}) is to be a solution mod 2^{n+1} that reduces mod 2^{n-1} to (x_{n}, y_{n}), then one must have

{
 x_{n+1} = x_{n} + 2^{n-1}s y_{n+1} = y_{n} + 2^{n-1}t

for some integers s, t. Then let

u_{n+1} = {5 x_{n+1}^{2} + 11 y_{n+1}^{2} - 1}/{2^{n+1}} .

u_{n+1} is certainly a rational number, and it is an integer if and only if 2^{n+1} u_{n+1} = 0 (mod 2^{n+1}).

After some computation one sees that the last condition becomes

2^{n} u_{n} + 2^{n}(5 x_{n} s + 11 y_{n} t) + 2^{2 n-2}(...) = 0 (mod 2^{n+1})

which is equivalent to

u_{n} + 5 x_{n} s + 11 y_{n} t = u_{n} + s = 0 (mod 2)

Thus, one has a solution (x_{n+1}, y_{n+1}) mod 2^{n+1} by choosing s = u_{n} mod 2 and t arbitarily. In fact, the free choice mod 2 for t is the reason why the number of solutions (x_{n}, y_{n}) mod 2^{n} is 2^{n}.