Every prime ≡ 1 (mod 4) is a sum of two squares

Step 1: $-1$ is a square modulo $p$. Let $m=\frac{p-1}2$, which is even. By Wilson, $-1\equiv(p-1)!=\prod_{k=1}^m k(p-k)\equiv\prod_{k=1}^mk(-k)=(-1)^m(m!)^2=(m!)^2\pmod p$. So $x=m!$ satisfies $x^2\equiv-1$.

Step 2: Thue's lemma. Let $s=\lfloor\sqrt p\rfloor$. Since $p$ is prime, it is not a square, so $s<\sqrt p<s+1$ and $(s+1)^2>p$. Consider the $(s+1)^2$ numbers
$$u+xv,\qquad0\le u,v\le s.$$
There are more of them than residues modulo $p$, so two different pairs $(u,v)\neq(u',v')$ satisfy $u+xv\equiv u'+xv'\pmod p$. Put $A=u-u'$, $B=v'-v$. Then $A\equiv xB\pmod p$, $|A|,|B|\le s<\sqrt p$, and $(A,B)\ne(0,0)$.

Step 3: conclusion. $A^2\equiv x^2B^2\equiv-B^2$, so $p\mid A^2+B^2$. Moreover $0<A^2+B^2<p+p=2p$. Hence $A^2+B^2=p$. Neither $A$ nor $B$ is $0$ (otherwise $p$ would be a square), so $p=|A|^2+|B|^2$ with positive integers.

Check. $p=13$: $x=6!=720\equiv5$, $25\equiv-1$ ✓, and $13=4+9$. $p=29=4+25$.

Lesson. Pigeonhole on a lattice of values forces a short vector in a congruence class (Thue's lemma); combined with $x^2\equiv-1$ it produces a sum of two squares.