# proof of Thue’s Lemma

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.

 $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

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. It is enough to show that if $m>1$, then there exists $(u,v,n)$ such that $1\leq n 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| and $|b|. We get

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

for some $n. 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 $np$ 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 ProofOfThuesLemma 2013-03-22 13:19:08 2013-03-22 13:19:08 mathcam (2727) mathcam (2727) 10 mathcam (2727) Proof msc 11A41