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.
 A: 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$.
A: $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.    
A: 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).
