proof of Thue’s Lemma


Let p be a prime congruentMathworldPlanetmath to 1 mod 4.

We prove the uniqueness first: Suppose

a2+b2=p=c2+d2,

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

p=c2+d2=p+4ax+4x2-4by+4y2,

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

mY=a+x=a+dX

and

mX=b-y=b-dY

for some positive integer m. Then

p=a2+b2=(mY-dX)2+(mX+dY)2=(m2+d2)(X2+Y2),

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)
1a[p]<p

(2) tells us

|ax-bp|<p.

Write u=|ax-bp|. We get

u2+a2a2x2+a20(modp)

and

0<u2+a2<2p,

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

u2+v2=np.

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

(x+y2)2+(x-y2)2=x2+y22

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

a2+b2=nm

for some n<m. But consider the identity

(a2+b2)(x2+y2)=(ax+by)2+(ay-bx)2.

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

nm2p=(ax+by)2+(ay-bx)2

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

x±(p-12)!(modp).
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