For $p$ odd, show that $p$ is prime in $\mathbb{Z}[i] \iff x^2+1$ does not have roots in $\mathbb{Z}/p\mathbb{Z}$ I am building on a previous question, where we showed that $\mathbb{Z}[x]/(x^2+1) \cong \mathbb{Z}[i]$. Now, I want to prove the statement in the title of this question.
First, let $p$ be an odd prime number. By definition, $p$ is prime in $\mathbb{Z}[i]$ if, whenever $p|ab$ for $a,b \in \mathbb{Z}[i]$, then $p|a$ or $p|b$. 
I feel like I have quite a few pieces. Firstly,
$$\mathbb{Z}[x]/(x^2+1) \cong \mathbb{Z}[i]$$
Then, if we let $(p)$ be the ideal in $\mathbb{Z}[i]$ or $\mathbb{Z}[x]$ generated by the odd prime $p$, then we can conclude
$$\mathbb{Z}[x]/(x^2+1)/(p) \cong \mathbb{Z}[i]/(p)$$
Finally by the proposition that, for any ring $R$, and $I$ and ideal of $R$, with $(I)=I[x]$ the ideal generated by $I$ in $R[x]$, then $R[x]/(I) \cong (R/I)[x]$, I want to assume that
$$\mathbb{Z}[i]/(p) \cong \mathbb{Z}/n\mathbb{Z}[i]$$
or, more generally
$$\mathbb{Z}[x]/(p) \cong \mathbb{Z}/n\mathbb{Z}[x]$$
I assume I need to use these pieces, but I not quite grasping how to tie the two sides together. I am having a harder time understanding how to use the right side, that $x^2+1$ does not have roots in $\mathbb{Z}/p\mathbb{Z}$. I am understanding this to mean $x^2+1 \ne 0 \mod p$. I also think I need to view $x^2+1$ as an element of $\mathbb{Z}[x]$, which would be the kernel of the map to $\mathbb{Z}[i]$. But, again, I cannot tie it all together.
 A: You're almost there:
$$
\mathbb{Z}[i]/(p)
\cong
\mathbb{Z}[x]/(p,x^2+1) 
\cong
(\mathbb{Z}/p\mathbb{Z})[x]/(x^2+1) 
$$
Then
$\mathbb{Z}[i]/(p)$ is a domain
$\quad$ iff $(\mathbb{Z}/p\mathbb{Z})[x]/(x^2+1)$ is a domain
$\quad$ iff $x^2+1$ is prime mod $p$
$\quad$ iff $x^2+1$ is irreducible mod $p$
$\quad$ iff $x^2+1$ has no roots mod $p$
(So we're actually talking about fields here.)
A: Actually, it’s a lot of (technical) abstract nonsense, as all your pieces are right. 
$x^2+1$ has no root in $\mathbb{Z}/p\mathbb{Z}$ iff $x^2+1$ is a prime element in $\mathbb{Z}/p\mathbb{Z}[x]$ (because it is a polynomial with degree 2). It occurs iff $\mathbb{Z}/p\mathbb{Z}[x]/(x^2+1)$ is an integral domain, iff $\mathbb{Z}[x]/(p,x^2+1)$ is an integral domain, iff $(\mathbb{Z}[x]/(x^2+1))/(p)$ is an integral domain, iff $\mathbb{Z}[i]/(p)$ is an integral domain, iff $p$ is a prime in $\mathbb{Z}[i]$. 
If you want a less abstract proof, here it is:
Assume that $x^2+1$ has a root $r \in \mathbb{Z}/p\mathbb{Z}$. Then let $r_0$ be an integer above $r$: then $r_0^2+1=(r_0+i)(r_0-i)$ is divisible by $p$, but neither $r_0+i$ nor $r_0-i$ is divisible by $p$. This proves $\Rightarrow$. 
Assume $p$ isn’t a prime in $\mathbb{Z}[i]$. Then there exists integers $a,b,c,d$ with $p$ not dividing $a+bi$ or $c+di$, but dividing $(a+bi)(c+di)=(ac-bd)+(ad+bc)i$. Then $p$ divides $(ac-bd)^2+(ad+bc)^2=(a^2+b^2)(c^2+d^2)$ thus $p$ divides eg $a^2+b^2$. As $p$ does not divide $a+bi$, there exists $b_1$ such that $p|bb_1-1$. Then $p|(ab_1)^2+1$, so that $ab_1 \in \mathbb{Z}/p\mathbb{Z}$ is a root of $x^2+1$. 
