How to factor polynomials in $\mathbb{Z}_{n}[x]$

Question

I realize there already is a question almost identical to this (here), but the answers given are a bit too vague. The problem I have is that I'm looking to factor the polynomial $$x^2+23x+18 \text{ in } \mathbb{Z}_{28}$$ into as many ways as possible. I've tried through trial and error since we're looking for $a,b \in \mathbb{Z_{28}}$ such that $$(x+a)(x+b)=x^2+23x+18$$ So $ab=18$ and $a+b=23$. But this seems too tedious and I haven't found an answer yet. So if anyone has a method for me to follow (sort of a recipe) or some clues as to how I can discover the method myself it would be much appreciated. Thanks.

Answer 1

Hint: Solve mod $4$ and mod $7$ and use the Chinese Remainder Theorem.

EDIT: OK, let's do the mod $4$ part. You want $$ x^2 + 3 x + 2 \equiv (x+a)(x+b) \mod 4 $$ Thus $$ \eqalign{a b &\equiv 2 \mod 4\cr a + b &\equiv 3 \mod 4\cr} $$ One of $a$ and $b$, let's say $a$, must be even, but can't be $0$, so it's $2$. Then the second equation tells you $b = 1$.

I'll let you do it mod $7$: let's say the result is $(x+c)(x+d)$, where $c$ and $d$ are different.

Now you'll have two possibilities for the factorization $(x+a)(x+b) \mod 28$, because the factors mod $4$ and the factors mod $7$ can pair up in two ways: either $$a \equiv 2 \mod 4, \; a \equiv c \mod 7, b \equiv 1 \mod 4, b \equiv d \mod 7$$ or $$a \equiv 2 \mod 4, \; a \equiv d \mod 7, b \equiv 1 \mod 4, b \equiv c \mod 7$$

In either case, once you have chosen $a$ and $b$ mod $4$ and mod $7$, CRT gives you the values mod $28$.

Answer 2

Factoring a polynomial over a ring that is not a domain is tricky because the degree of the factors need not be smaller than the degree of the original polynomial.

Indeed, over $\mathbb{Z}_{28}$ we have $$ x^2+23x+18 = (4x^2+8 x + 23)(7x^2+ 21x + 2) $$ which is somewhat surprising.

Answer 3

When there are zero divisor factoring a polynomial becomes very hairy. You have to define the terms very carefully to get much done. I suppose you can have fun with this, but I list a few things you need to be aware of:

• Are linear polynomials irreducible? Modulo $28$ we have "factorizations" like $$(7x-1)(8x+1)=-x-1.$$ The leading coefficients in the left are necessarily zero divisors, but?
• When the modulus is not square-free we have non-trivial units in the ring. Here $$(14x+1)^2=1.$$

For more information, check out:

• The sources Bill Dubuque dug out.
• More local discussion - not sure if they get to the bottom of it.