How to factor polynomials in $\mathbb{Z}_{n}[x]$ 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.
 A: 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.
A: 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$.
A: 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.

