View source for Kronecker method

{{TEX|done}}
A method for factoring a polynomial with rational coefficients into irreducible factors over the field of rational numbers; proposed in 1882 by L. Kronecker [[#References|[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|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 [[#References|[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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  L. Kronecker,   "Grundzüge einer arithmetischen Theorie der algebraischen Grössen"  ''J. Reine Angew. Math.'' , '''92'''  (1882)  pp. 1–122</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L.Ya. Okunev,   "Higher algebra" , Moscow  (1937)  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.G. Kurosh,   "Higher algebra" , MIR  (1972)  (Translated from Russian)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  B.L. van der Waerden,   "Algebra" , '''1–2''' , Springer  (1967–1971)  (Translated from German)</TD></TR></table>