Abstract Algebra/Factorization

One of the main motivations of this study is to determine the roots of a polynomial over a field. It is obvious that the roots of a product of polynomials is just their union (and in fact the multiplicities sum). Thus a good first step is to determine whether or not the given polynomial is a product of lower degree polynomials.

Recall we say a non-constant polynomial $f(x)\in F[x]$ is reducible if there exist non-constant polynomials $g(x)$ and $h(x)$ such that $f(x)=g(x)h(x)$. Otherwise, the polynomial is said to be irreducible. It is immediate that linear, i.e. degree 1, polynomials are irreducible. For low degree polynomials, it is easy to determine whether or not they are irreducible.

Lemma 4.2.1

If $f(x)\in F[x]$ is a degree 2 or degree 3 polynomial, it is reducible if and only if it has a root.

Proof. This simply amounts to noting that if $f(x)$ is of degree at most 3 then, any decomposition of the form $f(x)=g(x)h(x)$ must have at least one of $g(x)$ or $h(x)$ be linear. $\blacksquare$

Note that the statement does not hold for higher degree polynomials. For example $x^{4}-4$ has no roots in the rationals but $x^{4}-4=(x^{2}-2)(x^{2}+2)$ so it is reducible.

A case we are particularly interested in is polynomials over the rationals. A very useful theorem for this is the Rational Root Theorem which is a consequence of Gauss' Lemma.

Theorem 4.2.2 (Gauss' Lemma)

Let $f(x)\in \mathbb {Z} [x]$ be a primitive polynomial. Then $f(x)$ is irreducible over $\mathbb {Z} [x]$ if and only if it is irreducible over $\mathbb {Q} [x]$.

Proof. First we show that if $f(x)$ is reducible over $\mathbb {Q} [x]$ then it must be reducible over $\mathbb {Z} [x]$. Suppose we have $f(x)=g(x)h(x)$ where $g(x)$ and $h(x)$ are non-constant polynomials in $\mathbb {Q} [x]$. Suppose $d$ is the lowest common multiple of the denominators coefficients of the right hand side. Then$$df(x)=a(x)b(x)$$with $a(x),b(x)\in \mathbb {Z} [x]$. If $d=1$, we are done. So suppose $d>1$. We can write $d$ as a product of primes $d=p_{1}p_{2}\cdots p_{n}$. Modding out by $p_{1}$ we get$$0={\overline {a}}(x){\overline {b}}(x)$$where ${\overline {a}}(x),{\overline {b}}(x)$ are the corresponding polynomials in $\mathbb {Z} /p_{1}\mathbb {Z} [x]$ (in other words we mod each of the coefficients by $p_{1}$). Since $\mathbb {Z} /p_{1}\mathbb {Z} [x]$ is an integral domain, this means that at least one of the factors is 0. Without loss of generality we can assume that ${\overline {a}}(x)=0$. But this means that all of its coefficients are a multiple of $p_{1}$. Therefore we can cancel out $p_{1}$from both sides of the equation $df(x)=a(x)b(x)$. This leaves $n-1$ primes on the left hand side. We can apply the same argument and conclude via induction that $f(x)$ is reducible over $\mathbb {Z} [x]$.

The converse is easy to see since a decomposition over $\mathbb {Z} [x]$ is in particular a decomposition over $\mathbb {Q} [x]$. Since the coefficients don't share a factor this means that the decomposition is into a product of non-constant polynomials (in particular we avoid cases like $7x-7=7(x-1)$ which is a non-trivial decomposition in $\mathbb {Z} [x]$ but a trivial one in $\mathbb {Q} [x]$ since $7$ is only a unit in the latter ring).    $\blacksquare$

In particular this makes it easy to determine when a polynomial over the rationals has a rational root. Given $f(x)\in \mathbb {Q} [x]$, suppose it is monic with integer coefficients. Then if $f(x)$ has a root we can write $f(x)=(x-\alpha )(x^{n-1}+\cdots +\beta )$ where both factors have integer coefficients by Gauss' Lemma. Therefore in particular $\alpha$ is an integer and must be a factor of the constant polynomial. If $f(x)$ is not monic and its has a rational root $p/q$ then we would be able to write

$$f(x)=(px-q)(a_{n-1}x^{n-1}+\dots +a_{0})$$

In particular $p$ is a factor of the leading coefficient of $f(x)$ and $q$ is a factor of the constant term. This is known as the Rational Root Theorem. By trying all these possibilities, one can immediately determine whether or not there exist rational roots of a given polynomial over the rationals. (even if the coefficients are rational, one can multiply the polynomial by an integer to obtain a polynomial with integer coefficients and then work with this scaled polynomial, which has the same roots as the original).

Now that we know trying to reduce polynomials over $\mathbb {Q}$ is (essentially) equivalent to reducing them over $\mathbb {Z}$, it's useful to have some irreducibility criteria from the latter case. A very useful result for this is Eisenstein's criterion.

Lemma 4.2.3 (Eisenstein's Criterion)

Let $p$ be a prime in $\mathbb {Z}$ and $f(x)=x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}$ is a polynomial in $\mathbb {Z} [x]$. Suppose $p$ divides all the $a_{i}$ and $p^{2}$ does not divide the constant term $a_{0}$. Then $f(x)$ is irreducible over $\mathbb {Z} [x]$ and over $\mathbb {Q} [x]$.

Proof. Suppose $f(x)$ were reducible. Then there exist non-constant, monic polynomials $g(x),h(x)$ such that $f(x)=g(x)h(x)$. Consider the polynomial in the quotient $\mathbb {Z} /p\mathbb {Z}$. We find that$$x^{n}={\overline {g}}(x){\overline {h}}(x)$$

where ${\overline {g}}(x)$ and ${\overline {h}}(x)$ are the respective polynomials modulo $p$ (in other words ${\overline {g}}(x)=\pi _{*}(g(x))$ where $\pi :\mathbb {Z} \to \mathbb {Z} /p\mathbb {Z}$ is the canonical projection map). Since $g(x)$ and $h(x)$ were taken to be monic, we know their reductions ${\overline {g}}(x)$ and ${\overline {h}}(x)$ are also monic and hence non-constant. In particular then ${\overline {g}}(x){\overline {h}}(x)$ is a non-trivial decomposition of $x^{n}$.

By comparing coefficients above, we see that the product above has no constant term. Therefore at least one of ${\overline {g}}(x)$ and ${\overline {h}}(x)$ has no constant term (this is where we use the fact that $p$ is prime so in particular $\mathbb {Z} /p\mathbb {Z}$ is an integral domain). Suppose one of them does have a non-zero constant term. Then their product would contain lower degree terms but we know their product is exactly $x^{n}$. Therefore both ${\overline {g}}(x)$ and ${\overline {h}}(x)$ have no constant term. But this means the constant terms of $g(x)$ and $h(x)$ are both multiples of $p$ so in particular their product $a_{0}$ is a multiple of $p^{2}$ leading to a contradiction.     $\blacksquare$

Example: From Eisenstein's criterion, it is immediate that $x^{n}-2$ is irreducible over $\mathbb {Z}$ and hence over $\mathbb {Q}$ (by Gauss' Lemma). This is one way to show that ${\sqrt[{n}]{2}}$ are all irrational for $n\geq 1$.

Example: Here is a more sophisticated example. Consider the polynomial $$f(x)={\frac {x^{p}-1}{x-1}}=x^{p-1}+x^{p-2}+\cdots +x+1$$where $p$ is a prime. We observe that $$f(x+1)={\frac {(x+1)^{p}-1}{x}}={\frac {1}{x}}\sum _{k=1}^{p}{\binom {p}{k}}x^{k}=\sum _{k=0}^{p-1}{\binom {p}{k+1}}x^{k}$$In particular then $f(x+1)$ is a monic polynomial where every non-leading coefficient is a multiple of $p$ and the constant term is exactly $p$. Therefore by Eisenstein's criterion $f(x+1)$ is irreducible which in turn means that $f(x)$ is irreducible.

Once we have an irreducible polynomial, we know we can't decompose it any further so we need to start working with field extensions and splitting fields.

Exercises

1. Show that $x^{2}+x+1$ is irreducible over $\mathbb {F} _{2}$.
2. Find all irreducible polynomials of degree at most 3 over $\mathbb {F} _{2}$ and $\mathbb {F} _{3}$.
3. Show that $x^{2}+2$ is irreducible over $\mathbb {Q} (i)$.
4. Show that if ${\frac {x^{n}-1}{x-1}}$ is irreducible then $n$ is prime. Hint: Prove the contrapositive.