PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] proof of Thue's Lemma (Proof)

Let $ p$ 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 $ 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
$\displaystyle p=c^2+d^2=p+4ax+4x^2-4by+4y^2,$    

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
$\displaystyle mY=a+x=a+dX$    

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

for some positive integer $ m$. 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 $ p$ 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 $ a$ and $ b$ 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 $ u^2+a^2=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

$\displaystyle x^2 + y^2 = mp$ (3)

has a solution $ (x,y,m)$ with, we may assume, $ 1\le m<p$. It is enough to show that if $ m>1$, then there exists $ (u,v,n)$ such that $ 1\le n<m$ and
$\displaystyle u^2 + v^2 = np\;.$
If $ m$ is even, then $ x$ and $ y$ 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 $ n=m/2$ and conclude.

If $ m$ 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 $ n<m$. But consider the identity
$\displaystyle (a^2+b^2)(x^2+y^2)=(ax+by)^2+(ay-bx)^2\;.$
On the left is $ nm^2p$, 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 $ m^2$, getting an expression for $ np$ 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)

View style:


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 MSC11A41 (Number theory :: Elementary number theory :: Primes)

Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

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