# Methods to see if a polynomial is irreducible

Given a polynomial over a field, what are the methods to see it is irreducible? Only two comes to my mind now. First is Eisenstein criterion. Another is that if a polynomial is irreducible mod p then it is irreducible. Are there any others?

• Well, Eisenstein's criterion is basically a version of reducing modulo a prime. Aug 9, 2010 at 18:10
• See also this meta answer for grouped list of questions related to this topic math.meta.stackexchange.com/questions/1868/….
– Sil
Aug 11, 2018 at 11:13

## 7 Answers

To better understand the Eisenstein and related irreducibility tests you should learn about Newton polygons. It's the master theorem behind all these related results. A good place to start is Filaseta's notes - see the links below. Note: you may need to write to Filaseta to get access to his interesting book [1] on this topic.

[3] Newton Polygon Applet http://www.math.sc.edu/~filaseta/newton/newton.html

[4] Abhyankar, Shreeram S.
Historical ramblings in algebraic geometry and related algebra.
Amer. Math. Monthly 83 (1976), no. 6, 409-448.
http://links.jstor.org/sici?sici=0002-9890(197606/07)83:6%3C409:HRIAG...

• I'm not able to access the first link you posted Nov 24, 2010 at 11:18
• @crasic: Did you try contacting him to obtain access? Nov 24, 2010 at 14:08
• I would like to read this book too. May 4, 2011 at 11:42
• @Holdsworth88: So, ... two years later ... did you succeed or fail? Jun 29, 2014 at 5:23
• Failure. He never replied. Jul 3, 2014 at 19:19

One method for polynomials over $\mathbb{Z}$ is to use complex analysis to say something about the location of the roots. Often Rouche's theorem is useful; this is how Perron's criterion is proven, which says that a monic polynomial $x^n + a_{n-1} x^{n-1} + ... + a_0$ with integer coefficients is irreducible if $|a_{n-1}| > 1 + |a_{n-2}| + ... + |a_0|$ and $a_0 \neq 0$. A basic observation is that knowing a polynomial is reducible places constraints on where its roots can be; for example, if a monic polynomial with prime constant coefficient $p$ is reducible, one of its irreducible factors has constant term $\pm p$ and the rest have constant term $\pm 1$. It follows that the polynomial has at least one root inside the unit circle and at least one root outside.

An important thing to keep in mind here is that there exist irreducible polynomials over $\mathbb{Z}$ which are reducible modulo every prime. For example, $x^4 + 16$ is such a polynomial. So the modular technique is not enough in general.

• Incidentally, if a polynomial is irreducible in the algebraic closure of every prime field, then it is irreducible. (This is only interesting when one has a polynomial of multiple variables :)). This can be proved via an application of model theory: note that the statement "a given polynomial over $\mathbb{Z}$ is irreducible in some field" can be phrased via first-order logic. So if it is true in algebraically closed fields of arbitrarily high characteristic, it is true over $\mathbb{C}$, even. Aug 9, 2010 at 23:16

Here's an elementary trick that I occasionally find useful: Let $y=x+c$ for some fixed integer $c$, and write $f(x)=g(y)$. Then $f$ is irreducible if and only if $g$ is irreducible. You may be able to able to reduce $g$ modulo a prime and/or apply Eisenstein to show that $g$ is irreducible.

• Also works for $y=ax+c$. May 4, 2011 at 8:09
• ...if $a$ is a unit. Sep 8, 2011 at 23:09

Below is another method for irreducibility testing - excerpted from one of my old sci.math posts.

In 1918 Stackel published the following simple observation:

Theorem  If $$p(x)$$ is a composite polynomial with integer coefficients

then $$p(n)$$ is composite for all $$|n| > B$$, for some bound $$B$$,

in fact $$p(n)$$ has at most $$2d$$ prime values, where $$d = {\rm deg}(p)$$.

The simple proof can be found online in Mott & Rose [3], p. 8. I highly recommend this delightful and stimulating 27 page paper which discusses prime-producing polynomials and related topics.

Contrapositively, $$p(x)$$ is prime (irreducible) if it assumes a prime value for large enough $$|x|$$. Conversely Bouniakowski conjectured (1857) that prime $$p(x)$$ assume infinitely many prime values (except in trivial cases where the values of $$p$$ have an obvious common divisor, e.g. $$2 | x(x+1)+2$$ ).

As an example, Polya-Szego popularized A. Cohn's irreduciblity test, which states that $$p(x) \in {\mathbb Z}[x]$$ is prime if $$p(b)$$ yields a prime in radix $$b$$ representation (so necessarily $$0 \le p_i < b$$).

For example $$f(x) = x^4 + 6 x^2 + 1 \pmod p$$ factors for all primes $$p$$, yet $$f(x)$$ is prime since $$f(8) = 10601$$ octal $$= 4481$$ is prime.

Note: Cohn's test fails if, in radix $$b$$, negative digits are allowed, e.g. $$f(x) = x^3 - 9 x^2 + x-9 = (x-9)(x^2 + 1)$$ but $$f(10) = 101$$ is prime.

For further discussion see my prior post [1], along with Murty's online paper [2].

[1] Dubuque, sci.math 2002-11-12, On prime producing polynomials
http://groups.google.com/groups?selm=y8zvg4m9yhm.fsf%40nestle.ai.mit.edu

[2] Murty, Ram. Prime numbers and irreducible polynomials.
Amer. Math. Monthly, Vol. 109 (2002), no. 5, 452-458.
http://www.mast.queensu.ca/~murty/polya4.dvi

[3] Mott, Joe L.; Rose, Kermit. Prime producing cubic polynomials
Ideal theoretic methods in commutative algebra, 281-317.
Lecture Notes in Pure and Appl. Math., 220, Dekker, New York, 2001.
http://web.math.fsu.edu/~aluffi/archive/paper134.ps

Polynomials by Prasolov covers among others:

• Eisenstein's criterion
• Duma's criterion
• Irreducibility of polynomials attaining small values
• Hilbert's criterion
• Irreducibility of trinomials and fournomials
• A few algorithms for factorization

Reversing the polynomial. If you have polynomial with degree $$\geq 2$$ and non zero constant coefficients (otherwise it would be reducible so it wouldn't be interesting anyway), then you can reverse the coefficients and check irreducibility on that reciprocal polynomial. For example instead of checking $$f(x)=2x^4+2x^3+2x^2+2x+1$$, you can instead check $$x^4+2x^3+2x^2+2x+2$$ (and see it is irreducible by Eisenstein). This corresponds to $$x^4f(1/x)$$.

Another useful criterion is one provided by Ram's Murty in paper already referenced in the other answer, similar to Cohn's irreducibility criteria, it states:

Murty's irreducibility criterion: Let $$f(x)=a_mx^m+a_{m-1}x^{m-1}+\dots+a_1x+a_0$$ be a polynomial of degree $$m$$ in $$\mathbb{Z}[x]$$ and set $$H=\max_{0\leq i\leq m-1} |a_i/a_m|.$$ If $$f(n)$$ is prime for some integer $$n\geq H+2$$, then $$f(x)$$ is irreducible in $$\mathbb{Z}[x]$$.

You can see that for example $$f(x)=x^3-11x^2+19x-17$$ is irreducible because of that, if you try $$n=24$$.

Osada's criterion. Let $$f(x)=x^n+a_1x^{n-1}+\dots+a_{n-1}x\pm p$$ be a polynomial with integer coefficients, where $$p$$ is a prime. If $$p>1+|a_1|+\dots+|a_{n-1}|$$, then $$f(x)$$ is irreducible over $$\mathbb{Z}$$.

Following one is also simple to use, although I found it barely applicable, nevertheless interesting:

Brauer's criterion. Let $$a_1 \geq a_2 \geq \dots \geq a_n$$ be positive integers and $$n \geq 2$$. Then the polynomial $$p(x)=x^n-a_1x^{n-1}-a_2x^{n-2}-\dots-a_n$$ is irreducible over $$\mathbb{Z}$$.

Advanced criteria related to Newton polygons. These criteria are little bit more advanced to use, but the paper below provides plenty of corollaries in terms of prime powers (such as Eisenstein criterion, but in this case with multiple primes). Schönemann–Eisenstein–Dumas-Type Irreducibility Conditions that Use Arbitrarily Many Prime Numbers. An example: try to prove irreducibility of this one $$4x^6+108x^5+108x^4+108x^3+108x^2+108x+27.$$ The article above provides way to do this (it is first example in last section of examples).

Some related questions:

• Do you have any reference for Bauer's Criterion? Apr 18, 2019 at 17:00
• @N.S. Sure, check Polynomials by Victor V. Prasolov, it has Theorem 2.2.6 which is this criterion.
– Sil
Apr 18, 2019 at 17:39
• Perfect, thank you very much. Apr 18, 2019 at 22:57

A polynomial $$p$$ with coefficients in a field $$K$$ (ie. $$p \in K[x]$$) is irreducible if and only if $$K[x]/(p)$$ is a field. Therefore, all elements of this quotient ring are supposed to be invertible in that case. Say that $$p$$ is of degree $$n$$, then the elements in $$K[x]/(p)$$ are all of the form $$q(x) + (p)$$, where $$q$$ is a polynomial of degree $$n-1$$ or less. This means that inverting $$q$$ is equivalent to solving a linear system of equations. Thus, $$p$$ is irreducible if and only if $$q$$ may not be chosen such that this system is not solvable.

Thus, if $$M_q$$ is the matrix for $$q$$, the criterion is that $$\det(M_q) \neq 0$$ for all $$q$$ (because the inverse is unique, and invertibility is equivalent to the existence of a unique solution).

This reduces our problem to the solution of a polynomial equation in $$n$$ variables.

• Come to think of it, it would probably be easiest to reduce the general matrix to row echelon form and take note for which values of $q$ there arises a problem on the road to the identity. Mar 8 at 17:37