Proving $\left$ is not prime I am studying ring theory and stuck at this problem. The problem goes follows:
Let $\mathbb{Z}[i]=\{a+ib\mid a,b\in \mathbb{Z}\}$. Also, let $\omega = \frac{-1 + \sqrt{-3}}{2}$. We define $N(a+bi) = a^2 + b^2$ for all $a+bi \in \mathbb{C}$.
Let $p \ge 5$ be a prime number in $\mathbb{Z}$.

Prove that $\langle p \rangle$ is not prime in $\mathbb{Z}[i]$ if and only if there is a solution to $x^2 + 1 = 0$ in $\mathbb{Z}_p$.
Prove that $\langle p \rangle$ is not prime in $\mathbb{Z}[\omega]$ if and only if there is a solution to $x^2 - x + 1 = 0$ in $\mathbb{Z}_p$.

I don't have any idea how to start the proof. Can anyone help me on starting the proof?
 A: As J.W. Tanner commented, if there is a solution $x\in \{0,1,2,\dots,p-1\}$, to the equation $x^2+1\equiv0 \; \operatorname{mod} p$, then $p\mid x^2+1$, but this means $p\mid (x+i)(x-i)$ - since $x$ is real, the only way $p$ can divide either term (so that at least one term is in $\langle p\rangle$), is for us to have $p\mid 1$, which is clearly impossible.  
For the other direction, suppose $AX\in \langle p\rangle$, but $A\not\in\langle p\rangle$ and $X\not\in\langle p\rangle$. Let $A=a+bi$ and $X=x+yi$. Since $A\not\in\langle p\rangle$ and $X\not\in\langle p\rangle$, we conclude that $p$ does not divide each of $\_\_\_$, $\_\_\_$, $\_\_\_$, and $\_\_\_$. 
Since $AX\in \langle p\rangle$, we have $p\mid AX$ so that $p\mid AX\bar A\bar X=|A|^2|X|^2$. This means $p$ divides either $\_\_\_$ or $\_\_\_$.
Now, conclude the proof and try an analogous proof for $\mathbb Z[\omega]$.
Extra hint:

 $p$ divides one of $|A|^2$ and $|X|^2$. Suppose it divides $|A|^2=a^2+b^2$. Then $a^2+b^2\equiv 0 \;\operatorname{mod} p$. Since $A\not\in \langle p\rangle$, we know that $p\not \mid a$ (and $p\not\mid b$) so $a$ has a multiplicative inverse, $a^*$, $\operatorname{mod} p$. Multiply both sides of $a^2+b^2\equiv 0 \operatorname{mod} p$ by $(a^*)^2$  and conclude.

A: You have an isomorphism $$\phi:\Bbb Z[i]/(p)\rightarrow\Bbb Z_p[x]/(x^2+1)$$ Given by $$\phi(a+bi)=a+bx$$

*

*If $(p)$ is not prime, then for some $\alpha,\beta\in\Bbb Z[i]$, we have $\alpha\beta\in(p)$, but neither $\alpha,\beta$ are in $(p)$. Also, $\phi(\alpha\beta)=\phi(\alpha)\phi(\beta)=0$, but neither $\phi(\alpha),\phi(\beta)\neq 0$ so $\Bbb Z_p[x]/(x^2+1)$ has non-trivial zero-divisors. As $\Bbb Z_p[x]$ is an integral domain, we must have $x^2+1$ reducible, i.e., there is a solution to $x^2+1=0$ in $\Bbb Z_p$.


*If $(p)$ is prime, then $\Bbb Z[i]/(p)$ is an integral domain, so $x^2+1$ is irreducible, there are therefore no solution to $x^2+1=0$ in $\Bbb Z_p$.
