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
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
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
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
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
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
| { |
|
for some integers s, t. Then let
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
which is equivalent to
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}.