Kronecker method

A method for factoring a polynomial with rational coefficients into irreducible factors over the field of rational numbers; proposed in 1882 by L. Kronecker [1]. Let $d$ be a common denominator of the coefficients of a polynomial $\phi(x)$. Then $f(x)=d\phi(x)$ is a polynomial with integer coefficients; moreover, any factorization of $\phi(x)$ into irreducible factors with rational coefficients leads to a factorization of $f(x)$ into irreducible factors with integer coefficients, whose factors differ from the corresponding factors of $\phi(x)$ only by constant factors, and vice versa.

Let $f(x)$ be of degree $n>0$ and let $k$ be the largest natural number $\leq n/2$. If $f(x)=g(x)h(x)$ is a factorization of $f(x)$ into factors with integer coefficients, where the degree of $g(x)$ does not exceed that of $h(x)$, then the degree of $g(x)$ is at most $k$. Assigning to $x$ any $k+1$ distinct integer values $x=c_i$, $i=1,\dots,k+1$, one obtains equalities

$$f(c_i)=g(c_i)h(c_i),\quad i=1,\dots,k+1,$$

where $g(c_i)$ and $h(c_i)$ are integers. Thus, $g(c_i)$ divides $f(c_i)$. Choosing arbitrary divisors $d_i$ of the numbers $f(c_i)$, one obtains

$$g(c_i)=d_i,\quad i=1,\dots,k+1.$$

The polynomial $g(x)$ may now be determined from these equalities using the Lagrange interpolation formula, or, more simply, by the equations for the coefficients. It is then checked whether the polynomial $g(x)$ found in this way divides $f(x)$. This construction and the subsequent test are carried out for all possible choices of divisors of the numbers $f(c_i)$.

Subsequently, the same procedure is applied to $g(x)$ and $h(x)$, etc., until one obtains irreducible factors.

The Kronecker method involves cumbersome computations. It may be simplified by first lowering the degree of $f(x)$ by removing its rational roots (see [3]).

Example. $f(x)=x^5-x^4-2x^3-8x^2+6x-1$ (this is a polynomial with integer coefficients and without rational roots). If $f(x)=g(x)h(x)$, where the degree $k$ of $g(x)$ is at most that of $h(x)$, then $2\leq k<5/2$, i.e. $k=2$. With $c_1=0$, $c_2=1$, $c_3=2$ one has $f(0)=1$; $f(1)=-5$; $f(2)=-21$. The divisors of these numbers are $d_1=\pm1$; $d_2=\pm1,\pm5$; $d_3=\pm1,\pm3,\pm7,\pm21$. In all one has $2\cdot4\cdot8=64$ combinations. Since two combinations $d_i$ that differ only in sign yield the two polynomials $\pm g(x)$, it will suffice to check only $g(0)=+1$. There remain 32 cases. Running through all these cases, one finds only one polynomial of degree 2 dividing $f(x)$: $g(x)=x^2-3x+1$. Hence $f(x)=(x^2-3x+1)(x^3+2x^2+3x-1)$. Both factors are irreducible (as polynomials of degrees 2 and 3, respectively, without rational roots).

References

[1]	L. Kronecker, "Grundzüge einer arithmetischen Theorie der algebraischen Grössen" J. Reine Angew. Math. , 92 (1882) pp. 1–122
[2]	L.Ya. Okunev, "Higher algebra" , Moscow (1937) (In Russian)
[3]	A.G. Kurosh, "Higher algebra" , MIR (1972) (Translated from Russian)
[a1]	B.L. van der Waerden, "Algebra" , 1–2 , Springer (1967–1971) (Translated from German)