# Polynomial decomposition by Kronecker's method: usefulness of moduli

In B. L. van der Waerden's Algebra it's said that one can considerably simplify usage of Kronecker's method for polynomials over the ring of integers by factoring the given polynomial modulo 2 and possibly modulo 3, so that one gets an idea what degrees the possible factor polynomials might have, and to what residue classes the coefficients modulo 2 and 3 might belong.

I don't have a clue how that information might help. Can someone explain that? I would be really grateful for a little example too, that would help me for good.

Moreover, I might be wrong in understanding what is a polynomial modulo ring element. Is that just polynomial with coefficients modulo that element?

Suppose that $$p(x)$$, with integer or rational coefficients, factors over the rationals into $$p_1(x)p_2(x)...p_k(x)$$. Then, modulo $$q$$, it must factor in at least $$k$$ factors (not necessarily of the same degree).

So, the idea is that factorizations modulo $$q$$ gives you a bound from below on the number of irreducible factors over the rationals. In the extreme case that you find that modulo $$q$$ the polynomial is irreducible of the same degree, then the polynomial is forced to be irreducible over the rationals.

• Beware that the claim holds only for monic polynomials, e.g. $\, (30x+1)^n\,$ has $n$ prime factors in $\,\Bbb Z[x]\,$ but none $\bmod 2,3,5\ \ \$ Feb 3 '20 at 18:17
• @BillDubuque $0$ is a lower bound of $n$. For the implication about irreducibly one doesn't need to restrict to monic polynomials. It is enough to remember the degree of the original polynomial.
– Blue
Feb 3 '20 at 18:44
• Your claim implies $\,(30x+1)^n\,$ has at least $n$ factors $\!\bmod q$. That is false for $\,n\ge 1\,$ and $\,q = 2,3,5.\ \$ Feb 3 '20 at 19:13
• @BillDubuque There is no claim as to the nature of those factors. $(30x+1)^n$ modulo $2$ is $1\cdot 1\cdot ...\cdot 1$. One only needs to keep track of the degrees.
– Blue
Feb 3 '20 at 19:23
• Glad to see you edited it. Note also that a factor might even vanish $(\equiv 0)$ if the polynomial is not primitive. Feb 3 '20 at 19:41