If $p$ is a prime number and $p\equiv 1(mod 4)$, (show that) there exist integers $a$ and $b$ such that $a^{2}+b^{2}=p$.

Question

I'm reading a book on number theory (Theory of Numbers, Niven), and yesterday I've stumbled upon a proof of the above lemma (Lemma 2.13; page 54-55). I've managed to wrap my mind around the proof from the book, but it is really unintuitive and hard to follow(at least for me).

My question to you guys is do you know of any simpler and more intuitive proof of that particular lemma?

edit: here's the link for the proof from the book

Answer 1

If $p \equiv 1 \pmod 4$, then $-1$ is a square mod $p$. (This is proved quickly with Euler's Criterion, among other ways). So there is some $x$ such that $x^2 \equiv -1 \pmod p$, or rather $p \mid (x^2 + 1)$. Let's consider ourselves working within the Gaussian Integers $\mathbb{Z}[i]$, which is a Euclidean Domain (since we have a division algorithm) and therefore has unique factorization.

Since $p \mid (x^2 + 1)$, we see that $p \mid (x+i)(x-i)$. Since we do not have $p \mid (x \pm i)$, we see that $p$ is not a Gaussian prime. Therefore $p$ factors nontrivially as $p = z_1z_2$ for some $z_1, z_2 \in \mathbb{Z}[i]$.

Now let's consider norms of $p = z_1z_2$. The norm of $p$ is $p^2$. So we have that $p^2 = N(z_1)N(z_2)$. Since neither $z_1$ nor $z_2$ are units, they each are forced to have norm $p$. Now since $z_1 \in \mathbb{Z}[i]$, but is not in $\mathbb{Z}$ (since $p$ doesn't factor in $\mathbb{Z}$), we have that $z_1 = a + bi$ with $a,b \neq 0$. And the statement that the norm of $z_1$ is $p$ is exactly the statement that $a^2 + b^2 = p$.

Thus we have shown that $p \equiv 1 \pmod 4$ means that $p$ can be written as a sum of two squares (in a completely nonconstructive way). $\diamondsuit$

Answer 2

The lattice argument, as I recall it from Hardy and Wright:

As $p$ is 1 (mod 4) we can find $\lambda$ with $$\lambda^2 \equiv -1\,(mod\,p)$$ Define the lattice $\Lambda$ to be {$(m,n) \; m,n \in \mathbb Z\;\;m \equiv \lambda n \;(p)$} It is easy to convince yourself that the area of a fundamental parallelogram for $\Lambda$ is p (just count points in the lattice contained in a big circle). Let P = (a,b) be a point in $\Lambda$ closest to the origin. Then Q = (-b,a) is another minimal point in $\Lambda$ and it is easy to see that the Origin, P, and Q must be 3 vertices of a fundamental square for $\Lambda$. But the area of that square is clearly $a^2+b^2$.