PlanetMath: proof of Thue's Lemma

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (198)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

proof of Thue's Lemma

(Proof)

Let be a prime congruent to 1 mod 4.

We prove the uniqueness first: Suppose

$\displaystyle a^2+b^2=p=c^2+d^2,$

where without loss of generality, we can assume

and

even,

and

odd,

, and thus that

. Let

and

, and compute

$\displaystyle p=c^2+d^2=p+4ax+4x^2-4by+4y^2,$

whence

. If

, cancel the factor of

to get a new equation

with

, so we can write

$\displaystyle mY=a+x=a+dX$

and

$\displaystyle mX=b-y=b-dY$

for some positive integer

. Then

$\displaystyle p=a^2+b^2=(mY-dX)^2+(mX+dY)^2=(m^2+d^2)(X^2+Y^2),$

which contradicts the primality of

since we have both $m^2+d^2\geq 2$ and $X^2+Y^2\geq 2$ . We now proceed to existence.

By Euler's criterion (or by Gauss's lemma), the congruence

$\displaystyle x^2 \equiv -1 \pmod{p}$

(1)

has a solution. By Dirichlet's approximation theorem, there exist integers

and

such that

$\displaystyle \left\vert a\frac{x}{p}-b\right\vert\le\frac{1}{[\sqrt{p}]+1}<\frac{1}{\sqrt{p}}$

(2)

$\displaystyle 1\le a\le [\sqrt{p}]<\sqrt{p}$

(2) tells us

$\displaystyle \vert ax-bp\vert<\sqrt{p}\;.$

Write $u=\vert ax-bp\vert$ . We get

$\displaystyle u^2+a^2\equiv a^2x^2+a^2\equiv 0\pmod{p}$

and

$\displaystyle 0<u^2+a^2<2p\;,$

whence

, 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

$\displaystyle x^2 + y^2 = mp$

(3)

has a solution

with, we may assume, $1\le m<p$ . It is enough to show that if

, then there exists

such that $1\le n<m$ and

$\displaystyle u^2 + v^2 = np\;.$

is even, then

and

are both even or both odd; therefore, in the identity

$\displaystyle \left(\frac{x+y}{2}\right)^2+\left(\frac{x-y}{2}\right)^2=\frac{x^2+y^2}{2}$

both summands are integers, and we can just take

and conclude.

If is odd, write $a\equiv x\pmod{m}$ and $b\equiv y\pmod{m}$ with $\vert a\vert<m/2$ and $\vert b\vert<m/2$ . We get

$\displaystyle a^2+b^2=nm$

for some

. But consider the identity

$\displaystyle (a^2+b^2)(x^2+y^2)=(ax+by)^2+(ay-bx)^2\;.$

On the left is

, and on the right we see

$\displaystyle ax+by\equiv x^2+y^2$	$\displaystyle \equiv$	$\displaystyle 0\pmod{m}$
$\displaystyle ay-bx\equiv xy-yx$	$\displaystyle \equiv$	$\displaystyle 0\pmod{m}\;.$

Thus we can divide the equation

$\displaystyle nm^2p=(ax+by)^2+(ay-bx)^2$

through by

, getting an expression for

as a sum of two squares. The proof is complete.

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

$\displaystyle x\equiv\pm\left(\frac{p-1}{2}\right)!\pmod{p}\;.$

"proof of Thue's Lemma" is owned by mathcam. [ full author list (3) | owner history (1) ]

(view preamble)

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: sum of two squares, expression, right, identity, proof of Lagrange's four-square theorem, Thue's lemma, Dirichlet's approximation theorem, solution, Gauss' lemma, Euler's criterion, primality, integer, positive, equation, factor, odd, even, without loss of generality, congruent, prime

This is version 7 of proof of Thue's Lemma, born on 2002-12-25, modified 2006-05-13.
Object id is 3827, canonical name is ProofOfThuesLemma.
Accessed 4985 times total.

Classification:

AMS MSC:

11A41 (Number theory :: Elementary number theory :: Primes)

Pending Errata and Addenda

None.[ View all 2 ]

Discussion

forum policy

No messages.

Interact

post | correct | update request | add example | add (any)