Factorization of Polynomials - Kronecker's Method

Kronecker's Method

Since integer polynomials must factor into integer polynomial factors, and evaluating integer polynomials at integer values must produce integers, the integer values of a polynomial can be factored in only a finite number of ways, and produce only a finite number of possible polynomial factors.

For example, consider

.

If this polynomial factors over Z, then at least one of its factors must be of degree two or less. We need three values to uniquely fit a second degree polynomial. We'll use, and . Note that if one of those values were 0 then you already found a root (and so a factor). If none is 0, then each one has a finite amount of divisors. Now, 2 can only factor as

1×2, 2×1, (−1)×(−2), or (−2)×(−1).

Therefore, if a second degree integer polynomial factor exists, it must take one of the values

1, 2, −1, or −2

at, and likewise at . There are eight different ways to factor 6 (one for each divisor of 6), so there are

4×4×8 = 128

possible combinations, of which half can be discarded as the negatives of the other half, corresponding to 64 possible second degree integer polynomials that must be checked. These are the only possible integer polynomial factors of . Testing them exhaustively reveals that

constructed from, and, factors .

Dividing by gives the other factor, so that . Now one can test recursively to find factors of and . It turns out they both are irreducible over the integers, so that the irreducible factorization of is

(Van der Waerden, Sections 5.4 and 5.6)