Let $p$ be a prime congruent to 1 mod 4.

We prove the uniqueness first: Suppose

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

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

and

for some positive integer $m$. Then

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

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

(2) tells us

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

and

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

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

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

both summands are integers, and we can just take $n=m/2$ and conclude.

If $m$ is odd, write $a\equiv x\;\;(\mathop{{\rm mod}}m)$ and $b\equiv y\;\;(\mathop{{\rm mod}}m)$ with $|a|<m/2$ and $|b|<m/2$. We get

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

On the left is $nm^{2}p$, and on the right we see

Thus we can divide the equation

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