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