## 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 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) \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$$.

Ben Lynn blynn@cs.stanford.edu 💡