Primes of the form $a^2+b^2$ : a technical point.

One can classify the prime integers $p$ which can be written as $p=a^2+b^2$ for some integers $a,b\in\mathbb{Z}$ by studying how $p$ decomposes in the ring of Gauss integers $\mathbb{Z}[i]$.

Most proofs I have seen, at some point, reason as follows:

$p$ is a sum of two squares iff $p$ is non-irreducible in $\mathbb{Z}[i]$ iff $-1$ is a square in $\mathbb{Z}/(p)^*$.

In order to prove this, some ugly chain of isomorphisms $\mathbb{Z}[i]/(p)\simeq \ldots \simeq (\mathbb{Z}/(p))[X]/(X^2+1)$ is written down, and then one concludes that $X^2+1$ has a root in $\mathbb{Z}/(p)$ if $p$ is non-irreducible in $\mathbb{Z}[i]$.

My question is this: I find this chain of isomorphisms kind of ugly and unpleasant. Is there a more direct, conceptual way to see that $p$ is non-irreducible in $\mathbb{Z}[i]$ iff $-1$ is a square in $\mathbb{Z}/(p)^*$?

Solutions Collecting From Web of "Primes of the form $a^2+b^2$ : a technical point."

One first shows that Gaussian irreducibles $\pi$ have the basic property of ordinary primes, that if $\pi$ divides $\alpha\beta$ then $\pi$ divides $\alpha$ or $\beta$.

In a number-theory course, this is usually done by showing that the Gaussian integers are a Euclidean domain, so the primes are the (non-unit) irreducibles.

Suppose now that $c^2+1\equiv 0\pmod{p}$, where $p$ is an ordinary prime. Then $p$ divides $(c-i)(c+i)$. But $p$ clearly divides neither term in the product, so cannot be a Gaussian prime, and therefore cannot be irreducible.

Suppose $p = a^2 + b^2 \in \mathbb Z$ so $a^2 \equiv -b^2 \pmod p$ so just invert $b$ to find a modular square root of negative one $(b^{-1} a)^2 \equiv -1 \pmod p$.

For the other way around, if there is some integer $u$ satisfying $u^2 \equiv -1 \pmod p$ then $$\Lambda = \{(a,b) \in \mathbb Z^2 | b \equiv u a \pmod p\}$$ is a lattice (specifically take the diagonal $D = \{(a,ua)\in \mathbb Z^2|a\in \mathbb Z\}$ then $\Lambda = D + (0,p\mathbb Z)$ all the translates by $p$ up and down – so $\Lambda$ has basis vectors $\{(0,p),(1,u)\}$) with determinant $d(\Lambda) = 1\cdot p – u \cdot 0 = p$ so by Minkowski’s theorem any centrally symmetric convex body of volume $\ge 4p$ will contain a nontrivial lattice point, for example a circle with radius $r = \frac{2}{\sqrt{\pi}}\sqrt{p}$. Hence we have $(a,b) \in \Lambda$ (so $b \equiv u a \pmod p$) with $a^2+b^2 \le \frac{4}{\pi} p < 2p$ but by squaring the congruence we know $p|a^2+b^2$ so in fact $a^2+b^2 = p$!

Isn’t this all more related to unique factorization in $\mathbb Z[i]$?

We’ll stick to odd primes, $p$.

If $p|x^2+1$ then there is a $a+bi=\gcd(p,x+i)$. Necessarily, $a,b\neq 0$, since $a+bi|x+i$. Also, $a,b$ are relatively prime, and not both odd (or else $a+bi$ would be divisible by $1+i$, which would mean $p^2$ was divisible by $2$.)

So $a+bi|p$ and $a-bi|p$, and you can show that $a+bi$ and $a-bi$ are relatively prime. So by unique factorization, $(a+bi)(a-bi)=a^2+b^2|p$. But that clearly means that $a^2+b^2=p$.

On the other hand, of $-1$ is not a square, $\pmod p$, then any prime $a+bi|p$ necessarily has th property that $a^2+b^2|p^2$. So if $a,b\not\equiv 0\pmod p$, then $(a/b)^2+1\equiv \pmod p$ or $(b/a)^2+1\equiv 0 \pmod p$

The ugly chain of isomorphisms is a conceptual derivation.

As usual, it helps to turn interesting problems into algebraic problems, so that you can solve them with algebra. In this case, though, you’re not doing algebra with ring elements: you’re doing algebra with rings.

If you adjoin a square root of $-1$ (thus getting $\mathbb{Z}[i]$) then mod out by $p$, the properties of the resulting ring tell you whether the ideal $(p)$ is prime or not.

If you mod out by $p$ (thus getting $\mathbb{Z}/p$) and then adjoin a square root of $-1$, the properties of the resulting ring tell you whether $\mathbb{Z}/p$ has a square root of $-1$ or not.

The chain of isomorphisms you mention are just describing the fact that the two steps

  • Adjoin a square root of $-1$
  • Mod out by $p$

can be done in either order: you get the ‘same’ ring either way.

If one wasn’t sure of the fact that you get the ‘same’ result either way, one can do an ‘arithmetic’ calculation with whatever level of detail you like. That’s what the long chain of isomorphisms is: an arithmetic calculation with rings, done in sufficiently extreme detail so that you can see each individual step clearly.

Once you’re used to the arithmetic of rings, these calculations will be rather natural. e.g. I usually don’t think of $\mathbb{Z}[i]$ and $\mathbb{Z}[X]/(X^2+1)$ as being different, and would have gone straight from $\mathbb{Z}[i] / p$ to $\mathbb{F}_p[X] / (X^2 + 1)$ in a single step without giving it a second thought. (and would immediately know that it is given either by $i \to X$ or $i \to -X$)

Hint $ $ Mimic: $\rm\:mod\, 8\!:\, \pm\,1,3\ roots\ of\ x^2\!-\!1\Rightarrow\Bbb Z/8\ nondomain\:\Rightarrow\:8\ nonprime\:\Rightarrow\:8\ composite.$

In your case: $\rm\,\ mod\ p\!: \pm\,{\it i},n\ roots\ of\ x^2\!+\!1\:\Rightarrow \Bbb Z[{\it i}\,]/p\ nondomain\Rightarrow\! p\ nonprime\Rightarrow\! p\ composite.$