The factoring of polynomials

by ayushkhaitan3437

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.