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.


2 Answers 2


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}$.

  • $\begingroup$ @bateman: Thanks for spotting it. It is $c^2$. Fixed. $\endgroup$ May 24, 2013 at 18:49
  • $\begingroup$ I realized i can't understand why -in the first paragraph- $p$ does not divide neither $s-i$ nor $s+i$ $\endgroup$
    – bateman
    May 24, 2013 at 19:00
  • 1
    $\begingroup$ 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!) $\endgroup$ May 24, 2013 at 19:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .