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

We prove the uniqueness first: Suppose

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.

Remark:The solutions of the congruence (1) are explicitly $$x\equiv\pm\left(\frac{p-1}{2}\right)!\pmod{p}\;.$$