Sum of Two Squares

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, because it does not divide either of these factors.

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) \lt N(b)$.

We find $q$ with $N(a / b - q) \lt 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$.