proof of Thue's Lemma
ProofOfThuesLemma
2002-12-25 16:29:04
2006-05-13 12:35:04
Proof
Thue's lemma
0
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\PMlinkescapeword{squares}
\PMlinkescapeword{complete}
\PMlinkescapeword{divide}
Let $p$ be a prime congruent to 1 mod 4.
We prove the uniqueness first: Suppose
\begin{align*}
a^2+b^2=p=c^2+d^2,
\end{align*}
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
\begin{align*}
p=c^2+d^2=p+4ax+4x^2-4by+4y^2,
\end{align*}
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
\begin{align*}
mY=a+x=a+dX
\end{align*}
and
\begin{align*}
mX=b-y=b-dY
\end{align*}
for some positive integer $m$. Then
\begin{align*}
p=a^2+b^2=(mY-dX)^2+(mX+dY)^2=(m^2+d^2)(X^2+Y^2),
\end{align*}
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
\begin{equation}
x^2 \equiv -1 \pmod{p}
\end{equation}
has a solution. By Dirichlet's approximation theorem, there exist
integers $a$ and $b$ such that
\begin{equation}
\left|a\frac{x}{p}-b\right|\le\frac{1}{[\sqrt{p}]+1}<\frac{1}{\sqrt{p}}
\end{equation}
$$1\le a\le [\sqrt{p}]<\sqrt{p}$$
(2) tells us
$$|ax-bp|<\sqrt{p}\;.$$
Write $u=|ax-bp|$. We get
$$u^2+a^2\equiv a^2x^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
\begin{equation}
x^2 + y^2 = mp
\end{equation}
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
$$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^2p$, and on the right we see
\begin{eqnarray*}
ax+by\equiv x^2+y^2 & \equiv & 0\pmod{m} \\
ay-bx\equiv xy-yx & \equiv & 0\pmod{m}\;.
\end{eqnarray*}
Thus we can divide the equation
$$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.
\textbf{Remark: }The solutions of the congruence (1) are
explicitly
$$x\equiv\pm\left(\frac{p-1}{2}\right)!\pmod{p}\;.$$