A Nice Lemma In Congruence

Masum Billal
November 3, 2015

Abstract
Thue’s Lemma is a wonderful theorem in congruence. It should
have been quite popular, but unfortunately it not only isn’t very pop-
ular, it doesn’t have many resources from olympiad perspective when
searched in the internet, hence the article. In this article, we prove
this lemma and show some nice applications related to sum of squares
or quadratic residue. Thanks to anyone who helped in improving the
article, specially to user randomusername for providing links, ref-
erences of the problems and constructive suggestion. I have tried to
keep the article as self contained as possible. If there are still some-
thing the reader does not know, it may be assumed that the topic is
too common in AoPS.

1 Main Result
Theorem 1 (Thue’s Lemma). Let n > 1 be an integer and a √ be an integer
co-prime to n. Then there are integers x, y with 0 < |x|, |y| < n so that

x ≡ ay (mod n)

Such a solution (x, y) is called a small solution sometimes.

√
Proof. Let r = b nc i.e. r is the unique integer for which r2 ≤ n < (r + 1)2 .
The number of pairs (x, y) so that 0 ≤ x, y ≤ r is (r + 1)2 which is greater
than n. Then there must be two different pairs (x1 , y1 ) and (x2 , y2 ) so that

x1 − ay1 ≡ x2 − ay2 (mod n)

x1 − x2 ≡ a(y1 − y2 ) (mod n)

1
Let x = x1 − x2 and y = y1 − y2 , and we get x ≡ ay (mod n). Now, we need
to show that 0 < |x|, |y| < r and x, y 6= 0. Certainly, if one of x, y is zero,
the other is zero as well. If both x and y are zero, that would mean that
two pairs (x1 , y1 ) and (x2 , y2 ) are actually same. That is not the case, and
so both x, y can not be 0. Therefore, none of x or y is 0, and we are done.

Corollary 1. For a prime p and an integer a, there are integers x, y with

√
0 < |x|, |y| < p such that

x ≡ ay (mod p)

This lemma can be generalized even more with the same proof.

Theorem 2 (Generalization of Thue’s Lemma). Let α and β are two real

numbers so that αβ ≥ p. Then for an integer x, there are integers a, b with
0 < |a| < α and 0 < |b| < β so that,

a ≡ xb (mod p)

And we can even make this lemma a two dimensional one.

√
Theorem 3 (Two Dimensional Thue’s Lemma). Let n ≥ 2, r = n and
a, b, c, d be arbitrary integers. There exist w, x, y, z with at least one of y, z
non-zero such that

0 ≤ |w|, |x|, |y|, |z| ≤ r

w ≡ ay + bz (mod n)
x ≡ cy + dz (mod n)

2
2 Applications
First we show an elegant proof of Fermat’s 4n + 1 theorem here using a well
known theorem and Thue’s theorem (1).

Definition 1 (Bisquare). The sum of two perfect squares which are co-prime
to each other is a bisquare.

Definition 2 (Quadratic Residue). a is a quadratic residue of a prime p if

there exist an integer x so that,

x2 ≡ a (mod p)

a is a quadratic non-residue if there doesn’t exist any such integer x that,

x2 ≡ a (mod p)

Definition 3. Two integers a and b are co-prime if their greatest common

divisor (a, b) = 1. We denote this by a ⊥ b.

To prove Fermat’s theorem, we will use the following theorem without

proof, which is pretty well known and posted so many times on AoPS.

Theorem 4. −1 is a quadratic residue of a prime p if and only if p is of the

form 4n + 1.

Theorem 5 (Fermat’s 4n + 1 Theorem). Every prime of the form 4n + 1 can

be written as a bisquare.

Proof. We already know that, for p ≡ 1 (mod 4), there is an x so that,

x2 ≡ −1 (mod p)

From Thue’s theorem, for such an x, there are integers a, b with 0 < |a|, |b| <
√
p so that,

a ≡ xb (mod p)
a2 ≡ x2 b2 (mod p)
≡ −b2 (mod p)
a2 + b2 ≡ 0 (mod p)

3
The last congruence means that p|a2 + b2 , so
p ≤ a2 + b2 but
a2 + b2 < p + p
= 2p
Therefore, a2 + b2 = p must occur.

In fact, we can use the same technique for generalizing Fermat’s 4n + 1

theorem.
Theorem 6. Let n ∈ {−1, −2, −3}. If n is a quadratic residue of a prime p,
then there are integers a, b so that, a2 − nb2 = p.
Proof. We have already proven the case n = −1. If n is a quadratic residue
of p,
x2 ≡ n (mod p)
has a solution. Fix the integer x, and take a, b as in Thue’s lemma so that,
a ≡ xb (mod p)
a2 ≡ x2 b2 (mod p)
≡ nb2 (mod p)
p|a2 − nb2
We make two cases for n.
• n = −2. Then p ≤ a2 + 2b2 < p + 2p = 3p. So, either a2 + 2b2 = p or
a2 + 2b2 = 2p. If it’s the first, we are done. If not, we see that a must
be even. Assume a = 2a0 and we get p = b2 + 2a02 , as desired.
• Now, n = −3, so p ≤ a2 + 3b2 < p + 3p = 4p. If a2 + 3b2 = 2p, then a
and b are both odd or both even. If both are even, then 2p is divisible
by 4, a contradiction since p is odd. Otherwise, a and b are both odd.
a2 + 3b2 ≡ 1 + 3 · 1 (mod 4)
2p ≡ 0 (mod 4)
Again, contradiction. We are left with the case a2 + 3b2 = 3p. This
shows a is divisible by 3. If we take a = 3a0 , we get p = b2 + 3a02 .

4
Corollary 2. For a prime p and an integer n, there exists integers x, y so
that p divides x2 + ny 2 with p 6 |x, y if and only if −n is a quadratic residue
of p.

Proof. Without loss of generality, we can take x and y to be co-prime and n

not divisible by p. First assume, p|x2 + ny 2 , then y must be co-prime to p.
Therefore, y has an inverse modulo p, assume ay ≡ 1 (mod p).

a2 y 2 ≡ 1 (mod p)
p|a2 x2 + na2 y 2
p|a2 x2 + n
(ax)2 ≡ −n (mod p)

For the only if portion, we have −n is a quadratic residue of p, let k 2 ≡ −n

(mod p). Clearly, gcd(k, p) = 1 otherwise p will divide n. From Thue’s
lemma, there are integers x, y with

x ≡ ky (mod p)
x2 ≡ k 2 y 2 (mod p)
≡ −ny 2 (mod p)
p|x2 + ny 2

We can use these results to imply the following theorem also.

Theorem 7. For D ∈ {1, 2, 3}, if n = x2 + Dy 2 for some x ⊥ y, then every

divisor d of n is of the same form.

Proof. Remember the identity:

(a2 + Db2 )(c2 + Dd2 ) = (ac − Dbd)2 + D(ad + bc)2

= (ac + Dbd)2 + D(ad − bc)2

This means that the product of two numbers of the form x2 + Dy 2 is of

the same form. From theorems above, if p is a divisor of x2 + Dy 2 , then
p = a2 + Db2 for some a, b. The identity clearly says that, if m = a2 + Db2 ,

5
then any power of m, mk is of this form again. Let’s assume that, the prime
factorization of n is,
n = pe11 · · · pekk
k
Y
= pei i and
i=1
Yk
d= pfi i where 0 ≤ fi ≤ ei
i=1

From the lemma, for any 1 ≤ i ≤ k, pi is of this form. So, pfi i is of the same
form as well. So, for any divisor pf11 · pf22 is of the same form again. Repeating
this upto pfkk we get that, pf11 · · · pfkk = d is of the same form again.

Now we prove another theorem that demonstrates the power of Thue’s

theorem. We will use the following theorem without proof.
Theorem 8. −3 is a quadratic residue of p if and only if p is of the form
3k + 1.
Theorem 9. If p is a prime of the form 3k + 1, there are integers a, b such
that p = a2 + ab + b2 .
Proof. Since p is of the form 3k + 1, −3 is a quadratic residue of p. Take y
to be an odd integer for which p|y 2 + 3 or,
y 2 ≡ −3 (mod p)
Such an y exists, since p is odd. Even if y is even, y ≡ 2x + 1 (mod p) has a
solution. For that x, we get,
(2x + 1)2 ≡ −3 (mod p)
4x2 + 4x + 1 ≡ −3 (mod p)
4(x2 + x + 1) ≡ 0 (mod p)
x2 + x + 1 ≡ 0 (mod p)
because p is odd. From Thue’s theorem, there are integers a, b with 0 <
|a|, |b| < p such that,
a ≡ xb (mod p)

6
Then we also get

a2 + ab + b2 = a2 + a · ax + (ax)2
= a2 (x2 + x + 1)
≡ 0 (mod p)

Because p|a2 + ab + b2 , p ≤ a2 + ab + b2 . On the other hand,

p ≤ a2 + ab + b2
<p+p+p
= 3p

Either a2 + ab + b2 = p or a2 + ab + b2 = 2p. We can easily check that

a2 + ab + b2 = 2p can not happen (try yourself).

3 Problems
Assume that you know Thue’s lemma. How do we get that we need this par-
ticular lemma here? And how do we approach? If you saw the previous proof
of the sum of squares theorems, you should understand the main advantage
of using Thue’s lemma. The idea of small solutions is crucial here. For that,
we can bound some integers here.

Theorem 10. Let p > 5 be a prime so that, p divides k 2 + 5 for some integer
k. Show that, there are integers x, y such that, p2 = x2 + 5y 2 .

Problem 1. Let p be a prime for which there exists a positive integer a

such that p divides 2a2 − 1. Prove that, there exist integers b and c so that,
p = 2b2 − c2 .

Solution. We have 2a2 − 1 ≡ 0 (mod p). Since we want to bound 2b2 − c2 ,

it is obvious, we should find b, c so that p divides 2b2 − c2 and then bound
it. This is where Thue’s lemma comes in. Fix the integer a, which is clearly
co-prime to p. Then from Thue’s lemma, we there are integers b, c with
√
0 < |b|, |c| < p so that,

b ≡ ac (mod p)

7
This gives us what we need. Note that,

2b2 − c2 ≡ 2(ac)2 − c2
≡ c2 (2a2 − 1)
≡ 0 (mod p)

Thus, p divides 2b2 − c2 , and now we get to use the fact:

p ≤ 2b2 − c2
< 2b2 < 2p

We immediately get that p = 2b2 − c2 .

Problem 2 (Kömal). Let n be an integer. Prove that if the equation x2 +
xy + y 2 = n has a rational solution, then it also has an integer solution.
Problem 3 (Iran Olympiad, 3rd Round). Let p be a prime number. Prove
that, there exists integers x, y such that p = 2x2 + 3y 2 if and only if p ≡ 5, 11
(mod 24).
Problem 4 (Polish Math Olympiad Problem). Let S be a set of all positive
integers which can be represented as a2 + 5b2 for some integers a, b such that
a⊥b. Let p be a prime number such that p = 4n + 3 for some integer n. Show
that if for some positive integer k the number kp is in S, then 2p is in S as
well.
Problem 5 (Kömal). Prove that the equation x3 − x + 9 = 5y 2 has no
solution in integers.

References
[1] Kömal, Problem A 595, http://www.komal.hu/verseny/feladat.
cgi?a=feladat&f=A595&l=en

[2] Kömal, Problem A 618, http://www.komal.hu/verseny/feladat.

cgi?a=feladat&f=A618&l=en

[3] Kömal, Problem A 283, http://www.komal.hu/verseny/2002-01/A.

e.shtml