How can you prove that $f(x)=X^2+1$ is irreducible over $\mathbb Z_4$, the quotient ring?

We know that $\mathbb Z_4$ admits divisors of $0$, as $2*2=0$, so any elemanary approach using $h\times g=f$ doesn't necessarily lead us to $\text {deg}(h) = \text {deg}(g) = 1$ (as would have normally happened in $\mathbb Z$ or $\mathbb R$).

  • $\begingroup$ Showing it has no roots doesn't mean it is ireductible. Take X^4+X^2+1 in Z_2. It has no roots (neither 0 nor 1 are roots) but it can be written as (X^2+X+1)(X^2+X+1) $\endgroup$
    – Hemispherr
    Apr 5, 2016 at 20:36
  • $\begingroup$ I should note that in my notation, degree (h) is the largest power in that polynomial. $\endgroup$
    – Hemispherr
    Apr 5, 2016 at 20:41
  • 4
    $\begingroup$ The question of irreducibility in a non-integral domain is a bit subtle in many ways because of the presence of zero divisors. For example we have $$x^2+1=(2x+1)(2x^3+x^2+2x+1).$$ Yet we should not rush to declare the polynomial reducible. This is because here $2x+1$ is a unit in the ring $\Bbb{Z}_4[x]$. Namely $$(2x+1)^2=4x^2+4x+1=1.$$ Recall that an irreducible element is allowed to have unit factors (well, everything is divisible by all units). I'm not even sure about a fully satisfactory definition of an irreducible polynomial over $\Bbb{Z}_4$. $\endgroup$ Apr 5, 2016 at 21:01
  • 1
    $\begingroup$ In the late 90s coding theorists were heavily interested in the algebra of $\Bbb{Z}_4[x]$. IIRC when working with irreducible polynomials we only allowed monic factors. That approach lead to calculations like in Slade's answer (+1). We needed a good Hensel lifting theory, so this made sense. I may have forgotten a detail or three :-). IIRC the people who started that line of research used the conventions of MacDonald's book on Finite rings. Not sure that his conventions would be adopted universally. $\endgroup$ Apr 5, 2016 at 21:05
  • 1
    $\begingroup$ I'd like your comments Jyrki, but the site wouldn't let me. Crazy factorization, you nearly got me. $\endgroup$
    – Hemispherr
    Apr 5, 2016 at 21:12

1 Answer 1


Suppose we have a factorization $x^2+1=(x^2p + ax+b)(x^2q+cx+d)$ in $(\mathbb{Z}/4)[x]$, with $p,q\in (\mathbb{Z}/4)[X]$.

By unique factorization in $(\mathbb{Z}/2)[x]$, where $x^2+1=(x+1)^2$, this means that $a,b,c,d$ are odd, and $p=2f$, $q=2g$ are even.

Without loss of generality, assume $d\equiv 1\pmod{4}$. Multiplying out, we can see that $bd \equiv 1\pmod{4}$, so $b\equiv d\equiv 1$. But then the linear term is $a+c\equiv 0$. Perhaps switching the order of $f$ and $g$, this leads to the factorization:

$$x^2+1 = (2x^2f + x + 1)(2x^2g-x+1)$$

Multiplying out leads us to the equation $2x^2f(-x+1)+2x^2g(x+1) \equiv 2x^2\pmod 4$, or $f(-x+1) + g(x+1) \equiv (f+g)(x+1)\equiv 1\pmod{2}$, which is impossible by unique factorization.

  • $\begingroup$ Again, it seems to me like you are considering only a factorizarion in linear factors. What if we have higher degree polynomials that multiplied give f? $\endgroup$
    – Hemispherr
    Apr 5, 2016 at 20:55
  • $\begingroup$ Maybe this method can be extended though. I am not sure. Rings are funny business. $\endgroup$
    – Hemispherr
    Apr 5, 2016 at 20:57
  • $\begingroup$ @user4773863: Reduction modulo two is the right way to begin here. It shows that all the higher degree terms must be even. And those can be killed by multiplication with a unit of $\Bbb{Z}_4[x]$. $\endgroup$ Apr 5, 2016 at 21:08
  • $\begingroup$ I don't know how to implement Jyrki's proposed fix, but I've updated with a correction that should work. $\endgroup$ Apr 5, 2016 at 21:14

You must log in to answer this question.

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