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,

$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