# Motivation for the proof of Eisenstein's Criterion for irreducibility of polynomials

• Eisenstein Criterion for Irreducibility: Let $$f$$ be a primitive polynomial over a unique factorization domain $$R$$, say $$f(x)=a_0 + a_1x + a_2x^2 + \cdots + a_nx^n \;.$$ If $$R$$ has an irreducible element $$p$$ such that $$p\mid a_m\ \text{ for all }\ 0\le m\le n-1$$ $$p^2 \nmid a_0$$ $$p \nmid a_n$$ then $$f$$ is irreducible.

Can anyone give me an explanation of how one might have conjectured this problem? Thinking along, the same lines the first polynomial which came to my mind was $$x^{2}+1 \in \mathbb{R}[x]$$ which is irreducible. But there are lots of polynomials and it's very difficult to think of a condition, which would make them irreducible.

• See David Cox's paper "Why Eisenstein proved the Eisenstein criterion and why Schonemann discovered it first" cs.amherst.edu/~dac/normat.pdf Feb 26, 2011 at 18:27
• @Weaam The link is broken. Can you share the file? Thank you. May 27, 2020 at 6:19
• @GA316: maa.org/sites/default/files/images/upload_library/22/Ford/… works for now. I found it by googling the paper's name. Jul 3, 2021 at 16:41

The point is this: if $R \to S$ is a homomorphism and the image of $f$ is irreducible in $S[x]$, then $f$ must also be irreducible in $R[x]$ (since any factorization of $f$ in $R[x]$ maps to a factorization of $f$ in $S[x]$). This idea gets to the heart of what the point of homomorphisms is: they are maps that send algebraic statements ($f$ has a factorization) to other algebraic statements.

I guess the best motivated way to approach this is to make two choices for $S$. First we choose $S = \mathbb{Z}/p\mathbb{Z}$. This is a surprisingly useful choice for specific polynomials, especially of low degree (it works for some prime $p$ if and only if the Galois group of the polynomial $f$ contains a $\deg f$-cycle, which always happens in degree $2, 3$ and is still very likely in higher degrees). For example the polynomial $x^3 - x + 1$ must be irreducible because it has no roots $\bmod 2$.

At some point we might encounter a polynomial like $x^3 - 2x - 2$. Now this polynomial is reducible $\bmod 2$ since it factors as $x^3 = x \cdot x \cdot x$, but this implies that if $x^3 - 2x - 2$ had an actual factorization $fg$ in the integers then $f, g$ would both have to have all their non-leading terms divisible by $2$, hence the constant term of $fg$ is divisible by $4$; contradiction. Eisenstein's criterion is a simple generalization of this example; it corresponds to choosing $S = \mathbb{Z}/p^2\mathbb{Z}$ or $S = \mathbb{Z}_p$.

Nowadays it is understood that Eisenstein's criterion is really a statement about total ramification, but my guess is that this was not known when it was first written down. My guess is that Eisenstein wrote down this criterion for the sole purpose of proving that the cyclotomic polynomials $\Phi_p(x) = x^{p-1} + ... + 1$ are irreducible, and here it is very natural to think about what happens $\bmod p$ since $(x - 1) \Phi_p(x) = x^p - 1$ splits into linear factors $\bmod p$ by Fermat's little theorem. It is not a big leap from here to the general Eisenstein criterion.

• In the third paragraph, "...f,g would both have to have all their non-leading terms divisible by 2," I don't understand why this is true. Is there a theorem?
– Mark
Aug 19, 2011 at 3:19
• @Mark: the only possible factorizations of $x^3$ in $\mathbb{F}_2[x]$ have factors of the form $1, x, x^2, x^3$. It follows that the image of any factor over $\mathbb{Z}$ is congruent to $1, x, x^2$ or $x^3 \bmod 2$. Aug 19, 2011 at 3:38
• Ok that explains why the leading term isn't divisible by 2. But how does it follow that the rest of the terms of both f and g have to be divisible by 2? That's where I am stuck.
– Mark
Aug 19, 2011 at 3:48
• @Mark: suppose $f$ is an integer polynomial which is a factor of $x^3 - 2x - 2$. The argument above shows that $f(x) \equiv 1, x, x^2, x^3 \bmod 2$. This is equivalent to the statement that the non-leading terms of $f$ are divisible by $2$. Aug 19, 2011 at 3:51
• Oh Fermat's theorem. Shoot. Thanks for the clarification.
– Mark
Aug 19, 2011 at 3:58

Eisenstein's Criterion arises from exploiting factorization structure in a "simpler" image ring.  Here the structure exploited is simply that the image reduces to a $$\rm\color{#0a0}{prime\ power}$$, and prime products always factor $$\rm\color{#0a0}{uniquely}$$ in domains. Below we explore this viewpoint.

The first part of the hypothesis says: $$\bmod p\!:\ f \equiv a x^n\not\equiv 0\,$$ is ($$a$$ times) a $$\rm\color{#0a0}{prime\ power}$$ $$\:\!x^n$$

so a $$\rm\color{#c00}{proper}$$ factorization has form $$\, gh\equiv (b x^i) (c x^j)\,$$ for $$\,\color{#c00}{i,j \ge 1},\,$$ by $$\rm\color{#0a0}{uniqueness}$$ ($$\rm\color{#90f}{Lemma}$$)

But $$\,\color{#c00}{i,j \ge 1}\,\Rightarrow\, p\mid g(0),h(0)\,\Rightarrow\, p^2\mid g(0)h(0)\!=\!f(0),\,$$ contra second part of hypothesis.

Said in ideal language it is simply $$\,(p,x)^2\equiv (p^2)\,\pmod{\! x}$$

$$\rm\color{#90f}{Lemma}$$ $$\:x$$ prime, $$\,ax^n = fg\Rightarrow f = bx^i,\, g = cx^j,\ i\!+\!j=n,\ a=bc,\,$$ in any domain.

Proof  Induct on $$\,n.$$ $$\,n\!=\!0\,$$ clear. Else prime $$\,x\:\!|\:\! fg\,\Rightarrow\, x\:\!|\:\! f$$ or (wlog) $$\,x\:\!|\:\! g,\,$$ so $$\,ax^{n-1}\! = f(g/x),\,$$ so by induction $$f = bx^i,\ g/x = cx^j,\, i\!+\!j=n\!-\!1,\, a=bc,\,$$ so $$\,g = cx^{j+1},\, i+(j\!+\!1)=n$$.

Recall $$x$$ is prime in $$D[x]\!\iff\! D[x]/x\cong D\,$$ is a domain.

Remarks  With this view in mind one can easily generalize Eisenstein's criterion to other polynomials of similar shape, e.g. replace $$x$$ by a prime polynomial $$q$$ with $$\,f\equiv aq^n\!\pmod{\! p},\,$$ where $$\,\deg f = \deg q^n,\,$$ and $$\,p^2\nmid f\bmod q,\,$$ i.e. use $$\,(p,q)^2\equiv (p)^2\pmod{\! q}\,$$ similar to above.

This view also leads to the discriminant-based test for finding shifts $$x\mapsto x\!+\!c$$ that are Eisenstein, e.g. see this answer.

However, there is a limit to how far one can go since the criterion corresponds to totally ramified primes, but there are number fields without such primes (see e.g. Keith Conrad's note Totally ramified primes and eisenstein polynomials, and note that we can also apply Eisenstein to reversed (reciprocal) polynomials, as here)

In order to find fruitful generalizations one may apply valuation-theoretic ideas. The Eisenstein and related irreducibility tests are all special cases of much more general techniques exploiting Newton polygons. They yield the master theorem behind all these related results. An excellent comprehensive introduction can be found in Filaseta's lecture notes - see the links below. See also this MathOverflow question.

[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://mathdl.maa.org/mathDL/22/?pa=content&sa=viewDocument&nodeId=2964&pf=1

• This would profit from a definition of when a factorization counts as "proper". If you use the formal notion (i.e., neither factor is a unit), then it is not clear that a proper factorization in $R$ will always remain proper in $R/p$. You probably want "proper" to mean "both factors have degree $<n$" instead. Apr 5, 2023 at 21:02
• @darij I do not wish to obfuscate key ideas with minor details that should be obvious. In the past $12$ years (and $2208$ views!) not even one reader asked for clarification of the meaning of a "proper" factor here, so it is reasonable to infer that the meaning was obvious to students at this level. Posting a new dupe answer (and destroying dupe links) for such minor clarifications is very poor for site health since it leads to rampant duplication. Apr 6, 2023 at 0:05

If you don't know about ramification or valuations and things, there is still a great easy way to "see" Eisenstein from the $\mathbb{Z}[x]$ case. This is presented in Integers, Polynomials, and Rings by Ron Irving as a series of exercises to get the student to guess Eisenstein on their own.

First examine the case $x^n-p$ where $p$ is a prime. If this factors, then there are $f(x)=\sum_{k=0}^m a_kx^k$ and $g(x)=\sum_{k=0}^r b_kx^k$ for which $f(x)g(x)=x^n-p$. First, you get that $a_0b_0=p$ and hence without loss of generality $a_0=p$ and $p$ does not divide $b_0$ (we'll merely use this fact rather than $b_0=1$).

Now since $a_0b_1+a_1b_0=0$ we get that $p|(a_0b_1+a_1b_0)$ and $p|a_0$ so $p|a_1b_0$. This means $p|a_1$ or $p|b_0$, but $p$ does not divide $b_0$, so $p|a_1$. You can keep bootstrapping this argument up all the coefficients $a_k$ to get that $p|a_m$ the top coefficient, which is a contradiction since $a_mb_r=1$.

But what was really used here? Not much. So you could repeat the exact same argument with $x^n-pm$ where $(p,m)=1$. But that still isn't as general as you could go. You didn't need that $\sum_{j+k=l} a_jb_k=0$, you only needed that $p$ divided that sum to make the argument work, which is the same as checking that the polynomial $x^n+c_{n-1}x^{n-1}+\cdots +c_0$ has all $c_i$ divisible by $p$ (and $c_0$ not divisible by $p^2$).

Yet again, this still isn't as general as the argument allows you to go, because the contradiction only came from the fact that $p$ did not divide the leading coefficient, it wasn't that it was $1$.

So merely extrapolating what made the proof that $x^n-p$ is irreducible in $\mathbb{Z}[x]$ work gives you the full Eisenstein in $\mathbb{Z}[x]$. Lastly, if you want to go to $R[x]$, you need to figure out which facts about division you needed about $\mathbb{Z}$. But Eisenstein really is a criterion invented artificially in $\mathbb{Z}$ that could be guessed from examining what the key properties of one proof were.