# Factorization in Gaussian integers

Let $$p$$ be a natural number, suppose $$p$$ prime. Show that the following conditions are equivalent:

1. the polynomial $$x^2+1\in\mathbb{Z}_p$$ has roots in $$\mathbb{Z}_p$$

2. $$p$$ is reducible in the ring $$\mathbb{Z}[i]$$

3. there exists $$a,b\in\mathbb{Z}$$ such that $$p=a^2+b^2$$

My attempt: suppose $$x$$ is a solution of $$x^2=-1 \ mod\ p$$. Raising both sides to $$(p-1)/2$$ gives $$x^{p-1}=(-1)^{(p-1)/2}\ mod \ p$$. Suppose $$p$$ congruent to $$3$$ modulo $$4$$. Then $$(p-1)/2$$ is odd and $$(-1)^{(p-1)/2}=-1$$, while $$x^{p-1}=1$$, a contradiction. Hence $$p$$ must be congruent to $$2$$ modulo $$4$$, i.e. $$p=2$$ or $$p$$ congruent to $$1$$ modulo $$4$$, i.e. $$p=1+4n$$, some $$n$$.

If $$p=2$$ then $$p=(1+i)(1-i)$$ is reducible. If $$p=1+4n$$ i can't see how to show reducibility.

For $$2)\rightarrow 3)$$, suppose $$p=\alpha\cdot\beta$$ with $$\alpha,\beta$$ gaussian integers. Then the norm of $$\alpha$$, say $$a^2+b^2$$, divides $$p$$, but $$p$$ is prime and the norm can't be $$1$$, because the factorization of $$p=\alpha\beta$$ is not trivial, hence $$p=a^2+b^2$$.

Again, for $$3)\rightarrow 1)$$, i really don't know what to do. Thanks for any help.

Mapping $i$ to $x$, you can show that $$\mathbb{Z}[i] / (p) \cong \mathbb{Z}[x] / (p, x^2 + 1) \cong \mathbb{F}_p[x] / (x^2 + 1)$$ is an isomorphism of rings.

Now $\mathbb{F}_p[x]$ and $\mathbb{Z}[i]$ are both factorial rings, so $$p \; \mathrm{reducible} \; \Leftrightarrow p \; \mathrm{not} \; \mathrm{prime} \; \Leftrightarrow (x^2 + 1) \; \mathrm{not} \; \mathrm{prime} \; \Leftrightarrow x^2+1 \; \mathrm{has} \; \mathrm{a} \; \mathrm{zero}.$$

So it's enough to show $3 \rightarrow 2$, which is easy because then $p = (a+bi)(a-bi)$.

We deal first with the $p$ of shape $4n+1$ case you had trouble with. Suppose that the congruence has a solution $s$. Then $p$ divides $(s+i)(s-i)$. If $p$ were irreducible, it would be a Gaussian prime, so it would divide one of $s-i$ or $s+i$. But it doesn't.

For the other question, suppose $p=a^2+b^2$. Clearly $p$ divides neither $a$ nor $b$. Multiply $a^2+b^2$ by the square of the inverse $c$ of $b$ modulo $p$. We get $(ca)^2+1\equiv 0\pmod{p}$.

• @bateman: Thanks for spotting it. It is $c^2$. Fixed. May 24, 2013 at 18:49
• I realized i can't understand why -in the first paragraph- $p$ does not divide neither $s-i$ nor $s+i$ May 24, 2013 at 19:00
• Because $p$ doesn't divide $i$. When does an ordinary integer $k$ divide a Gaussian $a+bi$? When $a+bi=k(c+di)$ for some Gaussian $c+di$. This means $kc=a$ and $kd=b$, i.e. $a$ and $b$ are each an ordinary multiple of $k$. Now $s-i$ is $s+(-1)i$, and $k\gt 1$ does not divide $-1$. (I have done too much detail!) May 24, 2013 at 19:06