proof of Thue’s Lemma

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

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

(1)

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

\left|a\frac{x}{p}-b\right|\leq\frac{1}{[\sqrt{p}]+1}<\frac{1}{\sqrt{p}}

(2)

1\leq a\leq[\sqrt{p}]<\sqrt{p}

(2) tells us

|ax-bp|<\sqrt{p}\;.

Write $u=|ax-bp|$ . We get

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

and

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

x^{2}+y^{2}=mp

(3)

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

u^{2}+v^{2}=np\;.

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

\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 $|a|<m/2$ and $|b|<m/2$ . We get

a^{2}+b^{2}=nm

for some $n<m$ . But consider the identity

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

On the left is $nm^{2}p$ , 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

nm^{2}p=(ax+by)^{2}+(ay-bx)^{2}

through by $m^{2}$ , getting an expression for $n p$ as a sum of two squares. The proof is complete.

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

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

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