# Which primes $p$ in $Z$ remain primes in $Z[\sqrt{-1}]$?

Which primes $p$ in $Z$ remain primes in $Z[\sqrt{-1}]$? I don't just want to know which ones, I want to know how I find them.

-
Let me point you in this direction en.wikipedia.org/wiki/Gaussian_integer – Andreas Caranti Feb 4 '13 at 18:13
@AndréNicolas But $2$ splits not: it ramifies, rather than splits, right? – awllower Feb 5 '13 at 3:33
@awllower: Yes, I used the term informally, but it has a precise technical meaning. Made the same slip in the answer, since then corrected. – André Nicolas Feb 5 '13 at 3:43
Thanks for the attention then. – awllower Feb 5 '13 at 3:59

Since $2=(1+i)(1-i)$, let's consider the odd primes.

Suppose that $p=(a+bi)(a-bi)=a^2+b^2$. Since $p$ is odd and the only quadratic residues $\bmod{\,4}$ are $0$ and $1$, we must have that $p\equiv1\pmod{4}$. Thus, any $p\equiv3\pmod{4}$ is also prime in the Gaussian integers.

In fact, it is true that if $p\equiv1\pmod{4}$ then $p=a^2+b^2$ for some $a$ and $b$. Thus, if $p\equiv1\pmod{4}$, it is not a prime in the Gaussian integers.

Here is an excerpt from a paper I wrote a while ago that proves the last claim.

Claim: if $p$ is a rational prime, then either $p$ is a Gaussian prime or $p$ is the product of two conjugate Gaussian primes.

Proof: Since no rational prime other than $p$ can divide $p$, if $p$ is not a Gaussian prime, then the Gaussian prime factors of $p$ must appear in conjugate pairs. If there were $k$ conjugate pairs, each pair could be multiplied together to yield $k$ rational integers whose product is $p$. Thus, $k$ must be $1$. Therefore, if $p$ is not a Gaussian prime, $p$ is the product of a conjugate pair of Gaussian primes.
QED

Lemma: Suppose $p$ is a rational prime, then $p$ is a Gaussian prime if and only if $p\equiv3\pmod4$.

Proof: Suppose $p$ is not a Gaussian prime, then $p = (u+iv)(u-iv) = u^2 + v^2$ for some Gaussian prime $u+iv$. Thus, as the sum of two squares, $p\not\equiv3\pmod4$.

Suppose $p\not\equiv3\pmod4$. Then either $p = 2$ or $p\equiv1\pmod4$. If $p=2$, then $p=(1+i)(1-i)$, and $p$ is not a Gaussian prime. If $p\equiv1\pmod4$, then $(p-1)/4$ is an integer. The equation $x^{(p-1)/2} + 1 = 0$ has $(p-1)/2$ solutions in $\mathbb{Z}_p$. For any such solution, $x$, if $m=x^{(p-1)/4}$, then $m^2+1\equiv0\pmod p$. That is, $p\,|\,(m+i)(m-i)$, but $p$ divides neither $m+i$ nor $m-i$. Therefore, $p$ is not a Gaussian prime.
QED

A concern has been raised regarding the claim that factors appear in conjugate pairs.

Suppose that $(a+bi)(c+di)=k\in\mathbb{Z}$, where $\gcd(a,b)=1$ and $b\ne0$. Since $ad+bc=0$, we have $$c+di=-\frac db(a-bi)$$ and therefore, \begin{align} bk &=-d(a+bi)(a-bi)\\ &=-d(a^2+b^2) \end{align} Since $\gcd(a,b)=1$, $\gcd(a^2+b^2,b)=1$. Therefore, $(a+bi)(a-bi)=a^2+b^2\,|\,k$.

-
Your implicit assumption that the only possible factorizations of $p$ are of the form $\,p = \pi \bar \pi\,$ is a key point that requires proof. – Math Gems Feb 4 '13 at 18:27
The edit does not completely remedy the problem. What is the justifcation for the claim that the prime factors must occur in conjugate pairs? The proof depends crucially on these properties, so one cannot gloss over these matters. – Math Gems Feb 4 '13 at 18:37
@MathGems: something like $(a+bi)(c+di)\in\mathbb{R}$ then $ad+bc=0\Rightarrow\frac ab=-\frac cd$, thus real multiples of conjugates? – robjohn Feb 4 '13 at 18:38
And then how does the proposed proof proceed? There are many errors made by students attempting such proofs, so one needs to be very explicit when presenting such proofs if one wishes to convince a critical reader that the proof is free from such common blunders. – Math Gems Feb 4 '13 at 18:53
@MathGems: a section has been appended regarding conjugate pairs. – robjohn Feb 4 '13 at 19:23

$1.$ The prime $2$ can be expressed as $(1+i)(1-i)$.

$2.$ Primes of the form $4k+3$ don't split, and so remain prime. To see this, suppose to the contrary that such a prime $q$ can be expressed as $(a+bi)(c+di)$, where neither $a+bi$ nor $c+di$ is a unit. Then taking norms we find that $a^2+b^2=q$. This cannot happen.

For if $a^2+b^2=q$, then $a^2\equiv -b^2 \pmod{q}$. Multiplying by the inverse of $b$, we get that $-1$ is a quadratic residue of $q$. But it isn't.

$3.$ For primes $p$ of the form $4k+1$, one can use Fermat's result that every prime of the form $4k+1$ can be expressed as the sum $a^2+b^2$ of two squares. That gives the splitting $p=(a+bi)(a-bi)$.

Or else (better) use the standard fact that if $p$ is of the form $4k+1$, then $-1$ is a quadratic residue of $p$. It follows that there are integers $x$ and $k$ such that $x^2+1=pk$. Note that $x^2+1=(x+1)(x-i)$.

If $p$ is a Gaussian prime, then since $p$ divides $x^2+1$, it must divide $x+i$ or $x-i$. But it is clear that $p$ divides neither, so $p$ cannot be a Gaussian prime.

-
Ordinarily, when one says a prime “splits”, one means that there are at least two distinct primes upstairs corresponding. But this is not the case for $2$, whose behavior is quite different: $1+i$ and $1-i$ are related by the unit factor $i$. – Lubin Feb 4 '13 at 19:55
Thank you, the language was not careful enough there. Fixed. – André Nicolas Feb 4 '13 at 19:58

Show the following:

• A rational prime $p$ factors nontrivially if and only if $p=\pi\bar{\pi}$ for some $\pi\in{\bf Z}[i]$. Hint: suppose you have a factorization, notice that $p$ is invariant under conjugation, pair off the factors.
• $p=\pi\bar{\pi}$ for some $\pi\in{\bf Z}[i]$ if and only if $p=a^2+b^2$ for some integers $a,b\in{\bf Z}$.

Consider Fermat's theorem on sums of two squares (and the case $p=2$ separately).

-
I don't know if the conjugation argument works as given. It is shown that $p=\pi\tau=\bar{\pi}\bar{\tau}$. That is, both $\pi$ and $\bar{\pi}$ divide $p$. Now I believe it needs to be shown that $\gcd(\pi,\bar{\pi})=1$. – robjohn Feb 4 '13 at 20:14
@robjohn, factor $p$ all the way into irreducibles first as $\alpha_1\cdots\alpha_n$. (I suppose we do use UFDness for this.) And in any case, $\gcd(\pi,\bar{\pi})=\xi$ implies $|\xi|^2$ divides $p$ in the integers, so not much of an issue. – anon Feb 4 '13 at 20:43