Theorem: Every prime \(p = 1 \pmod{4}\) is a sum of two squares.

Proof: Let \(p = 4 m + 1\). By Wilson’s Theorem, \(n = (2 m)!\) is a square root of -1 modulo \(p\). (Alternatively, if \(g\) is a primitive root of \(\mathbb{Z}_p^*\) we may take \(n = g^m\).)

Thus \(p | n^2 + 1 = (n + i)(n - i)\). Therefore \(p\) is not irreducible in \(\mathbb{Z}[i]\), because it does not divide either factor.

Or is it? We overlooked a detail: how do we know primes and irreducibles are the same thing in \(\mathbb{Z}[i]\)?

We answer this by showing \(\mathbb{Z}[i]\) is euclidean with respect to the norm \(N(x+y i ) = x^2 + y^2\). That is, for any \(a,b \in \mathbb{Z}[i]\) and \(b\) nonzero, we find \(q,r \in \mathbb{Z}[i]\) with \(a = b q + r \) and \(N(r) < N(b)\).

We find \(q\) with \(N(a b - q) < 1\) via a geometric argument. The gaussian integers form a lattice, and \(a / b\) lies within norm 1 of at least one of the points on this lattice, and we can take any of them to be \(q\).

Thus \(\mathbb{Z}[i]\) is euclidean and hence a UFD, so all irreducibles are prime.

Now we’re sure \(p\) is reducible, namely \(p = (a+b i)(c + d i)\) for nonunits \(a + b i, c + d i\). Taking norms gives \(p^2 = (a^2 + b^2)(c^2 + d^2)\). Since neither factor of \(p\) has norm 1, we conclude that \(p = a^2 + b^2 = c^2 + d^2∎\)

Armed with this result, we can now easily describe the units and primes of \(\mathbb{Z}[i]\). The units are simply \(\pm 1, \pm i\), by considering elements of norm 1. As for the primes, if \(p = 3 \pmod{4}\) is a prime in \(\mathbb{Z}[i]\) then it is also prime in \(\mathbb{Z}[i]\) since in this case \(p\) cannot be the sum of two squares. Also if \(a^2 + b^2\) is prime, then \(a + b i\) is also a prime.

We claim there are no other primes. To see this, let \(\pi = a + b i\) be some prime in \(\mathbb{Z}[i]\). Then \(N(\pi) = p_1 p_2 ... p_k\) for some primes \(p_i\) in \(\mathbb{Z}\). This implies \(\pi | p\) for some prime \(p\) in \(\mathbb{Z}\), and hence \(N(\pi) = p\) or \(N(\pi) = p^2\). In the first case we have \(a^2 + b^2 = p\), and in the second, we see that \(p / \pi\) is an integer of norm 1 implying that \(\pi\) is an associate of \(p\). In the latter case, we must have \(p = 3 \pmod{4}\) otherwise it would contradict what we proved above.

We can also show that a positive integer is the sum of two squares if and only if it has the form \(a^2 b\) where \(b\) is squarefree and no prime factors equal to 3 modulo 4. This follows from the algebraic identity \((a^2 + b^2)(c^2 + d^2) = (a d - b c)^2 + (a c + b d)^2\), and the fact that the existence of nontrivial solutions of \(x^2 + y^2 = 0 \bmod p\) implies we can find a square root of -1 modulo \(p\), which is impossible if \(p = 3 \bmod 4\).