proof of Thue’s Lemma

Let p be a prime congruentMathworldPlanetmath to 1 mod 4.

We prove the uniqueness first: Suppose


where without loss of generality, we can assume a and c even, b and d odd, c>a, and thus that b>d. Let c=2x+a and d=b-2y, and compute


whence x(a+x)=y(b-y). If (x,y)=d, cancel the factor of d to get a new equation X(a+x)=Y(b-y) with (X,Y)=1, so we can write




for some positive integer m. Then


which contradicts the primality of p since we have both m2+d22 and X2+Y22. We now proceed to existence.

By Euler’s criterion (or by Gauss’s lemma), the congruenceMathworldPlanetmathPlanetmathPlanetmath

x2-1(modp) (1)

has a solution. By Dirichlet’s approximation theorem, there exist integers a and b such that

|axp-b|1[p]+1<1p (2)

(2) tells us


Write u=|ax-bp|. We get




whence u2+a2=p, as desired.

To prove Thue’s lemma in another way, we will imitate a part of the proof of Lagrange’s four-square theorem. From (1), we know that the equation

x2+y2=mp (3)

has a solution (x,y,m) with, we may assume, 1m<p. It is enough to show that if m>1, then there exists (u,v,n) such that 1n<m and


If m is even, then x and y are both even or both odd; therefore, in the identityPlanetmathPlanetmathPlanetmath


both summands are integers, and we can just take n=m/2 and conclude.

If m is odd, write ax(modm) and by(modm) with |a|<m/2 and |b|<m/2. We get


for some n<m. But consider the identity


On the left is nm2p, and on the right we see

ax+byx2+y2 0(modm)
ay-bxxy-yx 0(modm).

Thus we can divide the equation


through by m2, getting an expression for np as a sum of two squares. The proof is completePlanetmathPlanetmathPlanetmathPlanetmath.

Remark: The solutions of the congruence (1) are explicitly

Title proof of Thue’s Lemma
Canonical name ProofOfThuesLemma
Date of creation 2013-03-22 13:19:08
Last modified on 2013-03-22 13:19:08
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 10
Author mathcam (2727)
Entry type Proof
Classification msc 11A41