# 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. – Akhil Mathew Aug 9 '10 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 '18 at 11:13

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  on this topic.

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

 Abhyankar, Shreeram S.
Historical ramblings in algebraic geometry and related algebra.
Amer. Math. Monthly 83 (1976), no. 6, 409-448.

• I'm not able to access the first link you posted – crasic Nov 24 '10 at 11:18
• @crasic: Did you try contacting him to obtain access? – Gone Nov 24 '10 at 14:08
• I would like to read this book too. – quanta May 4 '11 at 11:42
• @Holdsworth88: So, ... two years later ... did you succeed or fail? – Eric Towers Jun 29 '14 at 5:23
• Failure. He never replied. – Holdsworth88 Jul 3 '14 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. – Akhil Mathew Aug 9 '10 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$. – Bruno Stonek May 4 '11 at 8:09
• ...if $a$ is a unit. – Bruno Stonek Sep 8 '11 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 , 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 , along with Murty's online paper .

 Dubuque, sci.math 2002-11-12, On prime producing polynomials

 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

 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, nvertheless interesting:

Bauer'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? – N. S. Apr 18 '19 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 '19 at 17:39
• Perfect, thank you very much. – N. S. Apr 18 '19 at 22:57