# Ireducible polynomial over $\mathbb Z_4$

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

• 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) Apr 5, 2016 at 20:36
• I should note that in my notation, degree (h) is the largest power in that polynomial. Apr 5, 2016 at 20:41
• 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$. Apr 5, 2016 at 21:01
• 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. Apr 5, 2016 at 21:05
• I'd like your comments Jyrki, but the site wouldn't let me. Crazy factorization, you nearly got me. Apr 5, 2016 at 21:12

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.

• 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? Apr 5, 2016 at 20:55
• Maybe this method can be extended though. I am not sure. Rings are funny business. Apr 5, 2016 at 20:57
• @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]$. Apr 5, 2016 at 21:08
• I don't know how to implement Jyrki's proposed fix, but I've updated with a correction that should work. Apr 5, 2016 at 21:14