# 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. 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$.

Graduate student