Different proofs for two squares theorem for primes

Question

There is a proof of two squares theorem for primes of form $4k+1$ from quadratic forms and there is a proof from Bolyai using Gaussian integers. I am reasonably sure such a nice simple statement has more than two proofs. What are the different proofs for the two squares theorem? Please provide one complete proof per answer.

Answer 1

I believe you're referring to an elementary result which maybe Fermat did actually prove.

If a prime number $p \,\in\, \mathbb{Z}^+ \,$ is the sum of two squares, then either that prime is $2$ or that prime is one more than a multiple of $4$. That is to say, if $p = m^2 + n^2$ has a solution in integers, then $p = 2$ or $p \,\equiv\, 1 \pmod 4 \,$.

This is easy enough to prove with modular arithmetic. If an odd number is the sum of two squares, then one square must be odd and the other even. If $m \equiv 2 \mod 4$, then $m^2 \equiv 0 \mod 4$. And if $m \equiv 3 \mod 4$, then $m^2 \equiv 1 \mod 4$. So $m^2 + n^2 \equiv 3 \mod 4$ is impossible, and therefore a prime of the form $4k + 3$ can't be the sum of two squares.