The factoring of polynomials

This article is about the factorization of polynomials:

First, I’d like to discuss the most important trick that is used directly or implicitly in most of the theorems given below. Let us consider the polynomial $f(x)=(a_mx^m+a_{m-1}x^{m-1}+\dots+a_0)(b_nx^n+b^{n-1}x^{n-1}+\dots+b_0)$ . Let $a_i$ be the first coefficient, starting from $a_0$ , not to be a multiple of $p$ in $a_mx^m+a_{m-1}x^{m-1}+\dots+a_0$ . Let $b_j$ be the first such coefficient in $b_nx^n+b^{n-1}x^{n-1}+\dots+b_0$ . Then the coefficient of $x^r$ in $f(x)$ where $r\leq i+j-1$ is definitely a multiple of $p$ , the coefficient of $x^{i+j}$ is definitely NOT a multiple of $p$ , and the coefficient of $x^t$ where $t>i+j$ , we can’t say anything about, except for the coefficient of $x^{m+n}$ which is definitely not a multiple of $p$ .

1. Gauss’s lemma (polynomial)- A primitive polynomial is one one with integer coefficients such that the gcd of all the coefficients is 1. The lemma states that if a primitive polynomial is irreducible over $\Bbb{Z}$ , then it is irreducible over $\Bbb{Q}$ . In other words, if a primitive polynomial has a root, it has to be an integer. The converse is also obviously true, as $\Bbb{Z\subset Q}$ . A very interesting proof can be found here, although Proof 1 is not completely correct. The characterization of $c_{i+j}$ should actually be $\sum\limits_{k\leq m,i+j-k\leq n}{a_k b_{i+j-k}}$ . This is to include the possibility of $i+j>m$ or $i+j>n$ . Also, note that in all other coefficients $a_rx^r\in f(x)g(x)$ , we are unlikely to find a glaring contradiction (that $p$ doesn’t divide this coefficient). This proof by explicit demonstration is indeed brilliant. But wait. This just proves that the product of primitive polynomials is primitive. It doesn’t prove that a primitive polynomial can only be factored into primitive polynomials. This proves the aforementioned. The most important thing to concentrate on here is the how to convert rational polynomials into a constant times a primitive polynomial. Any irreducible polynomial can be converted into a constant times a product of two primitive polynomials. It is only when the original polynomial is also primitive that this constant is $1$ .

2. Rational root theorem- It states that if a polynomial with integer coefficients has a rational root $\frac{p}{q}$ , then $p$ divides the constant and $q$ divides the leading coefficient (if the polynomial is $a_n x^n +a_{n-1}x^{n-1}+\dots +a_0$ , then $p|a_0$ and $q|a_n$ ). A proof is given here. I’d like to add certain things to the proof given in the article for a clearer exposition. First of all, by taking out the integral gcd of the coefficients, make the polynomial primitive. Let the gcd be $g$ . Deal with this primitive polynomial. Using Gauss’s lemma and the proof in the article, we can easily deduce that $q|\frac{a_n}{g}$ and $p|\frac{a_0}{g}$ . This both these are true, and as $g$ is an integer, we get $q|a_n$ and $p|a_0$ .

3. Eisenstein criterion- The statement and the proof are given here. I want to discuss the true essence of the proof. The most important condition is that $p^2\not| a_0$ . What this essentially does is it splits $p$ between $b_0$ and $c_0$ ; ie it can’t divide both. How does the splitting of $p$ change anything? We’ll come to that. Another important condition is that $p\not| a_n$ . This forces us to conclude that not all $b_i$ or $c_i$ are divisible by $p$ . Hence, there is a first element $b_r$ and a $c_t$ which are not divisible by $p$ . If $p\not|b_0$ , then $a_t$ is not divisible by $p$ , which contradicts the third condition that $p|a_i$ for $i<m+n$ . How? Because $a^t=b_0c_t+b_1c_{t-1}+\dots+b_tc_0$ .All terms except $b_0c_t$ are divisible by $p$ . This is where the splitting helped. If there was no such splitting (if $p^2|b_0c_0$ ) then $a_t$ could have been divisible by $p$ ). Similarly, if $p\not| c_0$ , then $p\not|a^r$ . Remember the point that I elaborated at the very beginning of the article? Try to correlate that with this proof. Here $a_{i+j}$ becomes $a_t$ or $a_r$ , as the first coefficient not to be divisible by $p$ is $b_0$ or $c_0$ .