Common Polynomial Irreducibility Criteria

Note: This explanation aims not only to prove common irreducibility criteria but to also demonstrate common methods used in the proofs which appear elsewhere.

There are several common irreducibility criteria for integer polynomials. But before, we can get into those, we need some background knowledge and setup. Define $\mathbb Z[x]$ as the set of polynomials with integer coefficients.

So $2x^2+4$ is irreducible because all we can factor out is a $2$, which is constant. But $x^2+5x$ is reducible because it factors as $x(x+5)$.

Now, I'll state some well-known and easy results that we'll need before proceeding onwards.

Gauss: A polynomial with integer coefficients which is irreducible in $\mathbb Q$ if and only if it is irreducible in $\mathbb Z$. (This means if we can factor it into polynomials with rational coefficients, we can factor it into polynomials with integer coefficients).

Obvious: An irreducible polynomial has no integer roots.

Now we may prove

Eisenstein's Criterion: If $P(x) = a_nx^n + a_{n-1} x^{n-1} + ... + a_0$, and some prime $p$ divides $a_0,a_1,a_2,..a_{n-1}$ but not $a_n$, and $p^2$ does not divide $a_0$, then $P$ is irreducible.

Suppose that $P(x) = Q(x) R(x)$ (this is the first step of almost any irreducibility proof) for $Q,R \in \mathbb Z[x]$ with $\deg Q, \deg R > 0$. I will write

$a_n x^n + a_{n-1} x^{n-1} + ... + a_0 = ( b_i x^i + b_{i-1} x^{i-1} + ... + b_0 )( c_{n-i} x^{n-i} + c_{n-i-1} x^{n-i-1} + ... + c_0)$.

Then taking this equation mod $p$, we know that $a_n x^n \equiv Q(x) R(x)$ mod $p$. Then some number theory tells us that $Q(x) \equiv q x^i, R(x) \equiv r x^{n-i}$ mod $p$ for some $r,q$ with $r \cdot q = a_n$.

This technique is called reduction mod p . Basically, it takes advantage of the fact that polynomials can be uniquely factored mod $p$, so if we take a polynomial mod a prime which its coefficients are divisible by, they all vanish!

But now suppose the constant term of $Q$ is $b_0$ and the constant term of $R$ is $c_0$. Since $Q$ is equivalent to $q x^i$, for $i>0$, its constant term vanishes, meaning we need $p|b_0$. Similarly, $p|c_0$.

But now take the constant term of $P$: It equals $b_0c_0$, and since $p|b_0, p|c_0$ we have $p^2|b_0c_0$. But take a look at the original criterion! We have stated $p^2 \not | a_0=b_0c_0$, so we have a contradiction!

This proof is instructive so we will summarize it: We have done two steps.

1. Write $P$ as $Q*R$ to obtain a contradiction.

2. Reduce $P$ mod a prime.

For an exercise, prove that $x^{p-1} + x^{p-2} + ... + 1$ is irreducible for a prime $p$.

Next, we will take a look at a strange criterion:

Cohn's Criterion, simplified: If a prime number may be expressed in base $10$ as $a_n 10^n + a_{n-1} 10^{n-1} + .. + a_0$ with $a_n>1$, then $P(x) = a_n x^n + a_{n-1} x^{n-1} + ... + a_0$ is irreducibile.

This is a very intuitive result: Basically it says that if you turn a prime into a polynomial, it remains "prime"!

As before, write $P(x) = Q(x) * R(x)$. But this time, we will examine and bound the roots of $P$.

Note that in base $10$, all digits are less than $10$. So we have $0 \le a_i < 10$ for all $i$.

Now take an arbitrary root $r$ of $P$. Since $a_n r^n = - a_{n-1} r^{n-1} - ... - a_0$, we have

$| a_n r^n | = | a_{n-1} r^{n-1} + a_{n-2} r^{n-2} + ... + a_0|$.

Since $a_n > 1$ we have $a_n \ge 2$. Thus

$LHS \ge 2 | r|^n$.

Meanwhile, by the extended triangle inequality, we have

$|a_{n-1} r^{n-1} + a_{n-2} r^{n-2} + ... + a_0| \le |a_{n-1} r^{n-1}| + |a_{n-2} r^{n-2} | + ... + |a_0|$

This last quantity equals

$a_{n-1} |r|^{n-1} + a_{n-2} |r|^{n-2} + ... + |a_0| \le 9 |r|^{n-1} + 9 |r|^{n-2} + ... + 9$.

Thus, we have $2 |r|^n \le 9 |r|^{n-1} + 9 |r|^{n-2} + ... + 9$.

If $|r| \ge 9$, then we have $LHS > RHS$, which is a contradiction! (You can prove this via the geometric series formula on the RHS and then cross-multiplying, but I'll leave it out).

Thus we know that all roots of $P$ have magnitude less than $9$.

Let the roots be $r_1,r_2,...r_n$. Note that $P(10) = Q(10) R(10)$ so one of $Q(10), R(10)$ is $\pm 1$ since $P(10)$ is prime. WLOG let it be $Q(10)$, and suppose it equals $1$. Then

$1=Q(10) = b \prod (10 - r_i)$ for some positive integer $b$ and some roots $r_i$ which are also roots of $P$.

But $|b \prod (10 - r_i) | = |b| \prod |10 -r_i|$ and since $|r_i| < 9$, we have $|10 - r_i| > 1$. So then $1=Q(10) > b \ge 1$, a contradiction. Thus $P$ is irreducible as desired.

This emphasizes another technique: Bound the roots of the polynomial

In case you are not familiar with it, we have one final common irreducibility criteria using root-bounding:

Ostrowski: Let $P(x) = a_nx^n + a_{n-1} x^{n-1} + ... + a_0 \in \mathbb Z[x]$. If $|a_0|$ is prime and $|a_0| > |a_1| + |a_2| + ... + |a_n|$, $P$ is irreducible.

Proof: I'll just go over it very quickly since this is quite repetitive.

Write $P(x) = Q(x) R(x)$, and since $|a_0|$ is prime, the constant term of one of $Q,R$ equals $1$. WLOG suppose the constant term of $Q$ is 1. Take any root $r$ of $P$.

Then using the same technique as earlier, we have that $|a_0| \le |a_1| |r| + |a_2| |r|^2 + ... + |a_n| |r|^n$.

If $|r| \le 1$, then we get

$a_0 \le |a_1| + |a_2| + ... + |a_n|$, a contradiction! Thus all roots have $|r|>1$.

But then the constant term of $Q$ is the product of many terms of the form $r_i$, so its magnitude is greater than $1$, a contradiction.

Conclusion:

Today we proved three irreducibility criterion: Eisenstein, Ostrowski, and Cohn, and skimmed over Gauss's Lemma. We also noticed some common techniques for proving irreducibility: Reduction mod $p$, root-bounding, and contradiction.

If you want some more irreducibility criterion, I'll give you some names:

Perron's Criterion: If $P(x) = x^n+a_{n-1} x^{n-1} ... +a_0$, and $a_0 \neq 0$, with $|a_{n-1} | > 1 + |a_{n-2} | + ... + |a_0|$, then $P$ is irreducible.

STronger Cohn: Same statement as Cohn, except it covers the $a_n=1$ case.

Cyclotomic Irreducibility: The $n$th cyclotomic polynomial $\Phi_n (x)$ is irreducible.

Irreducibility is a wide topic, and there are many other criterion. Have fun finding them!

Perron's Criterion

Let $f(x) = x^n + a_{n - 1}x^{n - 1} + ... + a_1x + a_0$ be a polynomial with integer coefficients with $a_0 \neq 0$ and

$|a_{n - 1}| > 1 + |a_{n - 2}| + ... + |a_1| + |a_0|$.

Then $f(x)$ is irreducible.

This is a really nice result. For example, this solves the following IMO problem instantly :

Prove that the polynomial $x^n + 5x^{n - 1} + 3$ is irreducible over the integers.

The proof follows from Perron's criterion and the fact that

"Five is greater than one plus three"!

($5 > 1 + 3$)

Prove that $x^{p-1}+x^{p-2}+\ldots+1$ is irreducible for a prime $p$.

Hint: Replace $x$ by $x+1$.

Let $f(x) = x^n + 5x^{n-1} + 3$, where $n > 1$ is an integer. Prove that $f(x)$ cannot be expressed as the product of two non-constant polynomials with integer coefficients.