  ## Factoring, the Binomial Theorem, and Eisenstein's Criterion

Taking a cue from integers, where "factoring" means to write an integer as a product of other integers, we take "factoring polynomials" to similarly mean writing a polynomial as a product of other polynomials.

We shall ultimately see that factoring a general polynomial is a difficult task, but there are certainly many polynomials that can be factored relatively easily. The following details some commonly encountered types of polynomials (some of multiple variables) where such factorizations are easy to find.

### Monomial Factors

Monomial factors are the easiest to identify. One simply needs to ask oneself: "What single-term factor(s) does every term of the polynomial in question share?" Then, use the distributive property in reverse to pull these common factors out as a monomial (possibly of several variables). As an example, if we wished to factor $10x^2y^3z + 4x^2y$, we would note that $10x^2y^3z$ and $4x^2y$ share factors of $2$, $x^2$, and $y$. Thus, $$10x^2y^3z + 4x^2y = 2x^2y(5y^2z + 2)$$

### Squares, Cubes, and Higher Powers of Binomials

Factorization rules for the squares and cubes of binomials can be obtained by simply expanding the related products, as shown below

$$\begin{array}{rcl} (x+y)^2 &=& x^2 + xy + xy + y^2\\ &=& x^2 + 2xy + y^2\\\\ (x+y)^3 &=& (x+y)(x+y)^2\\ &=& (x+y)(x^2 + 2xy + y^2)\\ &=& x(x^2 + 2xy + y^2) + y(x^2 + 2xy + y^2)\\ &=& x^3 + 2x^2y + xy^2 + yx^2 + 2xy^2 + y^3\\ &=& x^3 + 3x^2y + 3xy^2 + y^3 \end{array}$$

Reversing these results, we arrive at the factorization rules:

$$\boxed{\displaystyle{\begin{array}{rcl} x^2 + 2xy + y^2 &=& (x+y)^2\\ x^3 + 3x^2y + 3xy^2 + y^3 &=& (x+y)^3 \end{array}}}$$

When we see polynomials that follow one of the above patterns, factoring them becomes easy. For example,

$$\begin{array}{rcl} 9a^2 + 12ab^3 + 4b^6 &=& (3a)^2 + 2(3a)(2b^3) + (2b^3)^2\\ &=& (3a + 2b^3)^2 \end{array}$$

We could find rules for higher powers of a binomial through a similar process. Interestingly, a pattern seems to emerge when we do so. Consider the powers $(x+y)^n$ as $n$ takes on integer values from $0$ to $4$, inclusive: $$\begin{array}{c} (x+y)^0 = 1\\ (x+y)^1 = x + y\\ (x+y)^2 = x^2 + 2xy + y^2\\ (x+y)^3 = x^3 + 3x^2 y + 3xy^2 + y^3\\ (x+y)^4 = x^4 + 4x^3 y + 6x^2 y^2 + 4x y^3 + y^4\\ \end{array}$$ For each such $n$, when we arrange the terms (as above) so that the exponents on $x$ descend from left to right, note that they do so by $1$ each time. As they do, the exponents on $y$ ascend by the same amount. In this way, the sum of the exponents on $x$ and $y$ remains $n$.

There is a pattern to the coefficients as well.

First notice that the first and last coefficients are always both equal to $1$. This should not be surprising, as when expanding $(x+y)^n$, there is only one way to generate the $x^n$ term -- by multiplying all the $x$ terms from each factor together. Similarly, there is only one way to generate the term with no $x$ factors (namely, $y^n$) -- by multiplying all the $y$ terms from each factor together.

Focusing on the rest of the coefficients, however, is where things get really intriguing!

Suppose we write just the coefficients seen in $(x+y)^n$ in a triangular arrangement mirroring the calculations above. We do this below on the left. As the animated image on the right suggests, each coefficient appears to be the sum of the two coefficients directly above. We can easily prove this continues to be true for all subsequent rows corresponding to $n=5,6,7,\ldots$ This "triangle of coefficients" constructed from $(x+y)^n$ is known as Pascal's Triangle.  While named after the $17^{th}$ century mathematician and philosopher Blaise Pascal, who used the triangle to solve probability problems and discovered and proved many interesting properties concerning it -- he was not the first person to study it. The Persian mathematician and engineer Al-Karaji, who lived from 935 to 1029 is currently credited with its discovery. (Interesting tidbit: Al-Karaji also introduced the powerful idea of arguing by mathematical induction.) Another Persian mathematician, Omar Khayyam popularized Al-Karaji's work to the point that even now in Iran, the triangle is often referred to as Khayyam's Triangle.

The triangle also showed up in China, well before Pascal worked with it. Chinese mathematicians Jia Xian and (later) Yang Hui also represented coefficients of binomial powers this way, and found interesting properties between the numbers contained in the triangle. In China, the triangle is called Yang Hui's triangle.

Even in Europe, there are multiple people associated with the triangle before Pascal. Notably, Petrus Apianus is responsible for the first printed record of the triangle when he used it as the frontispiece of a book in 1527. In Italy, the triangle is known as Tartaglia's triangle, named after the Italian algebraist Niccolo Tartaglia who published six rows of the triangle in 1556. (Interestingly, Tartaglia plays a prominent role in solving higher-order polynomial equations, on which we will focus considerable attention a bit later.) Gerolamo Cardano too (who also plays a significant role in our story to come), published the triangle and various ways of constructing it in 1570 -- again, well before Pascal.

As alluded to in its history, there are many patterns to the values in Pascal's triangle. One was mentioned above, whereby each row can be quickly constructed from the previous row. However, there is another, much more important (and provable) pattern that can be exploited to produce the numbers on any single row even faster, and without reference to any other rows. This elegant result, known as the Binomial Theorem then lets us expand $(x+y)^n$ for any non-negative integer $n$ as: $$(x+y)^n = x^n + {}_nC_1 x^{n-1} y + {}_nC_2 x^{n-2} y^2 + {}_nC_3 x^{n-3} y^3 + \cdots + {}_nC_{n-1} x y^{n-1} + y^n$$ Should the notation ${}_n C_k$ be unfamiliar (some texts denote this by ${n \choose k}$ instead), it calculates the number of combinations of $n$ things, taken $k$ at a time that one can form. That is to say, it counts the number of ways one can choose a set of $k$ objects when drawing from a group of $n$ objects. Students having seen some probability or statistics will likely know its value can be computed with the formula: $${}_n C_k = \frac{n!}{k!(n-k)!}$$ where $m!$, called the factorial of $m$ is defined by $m! = m \cdot (m-1) \cdot (m-2) \cdots 3 \cdot 2 \cdot 1$.

To see how these ideas are connected, consider the terms of the expansion of

$$(x+y)^n = \underbrace{(x+y)(x+y)(x+y) \cdots (x+y)}_{n \textrm{ factors}}$$

Ultimately, each term of the expansion is formed by choosing either an $x$ or a $y$ from the first factor, and then choosing either an $x$ or a $y$ from the second factor, and then choosing an $x$ or a $y$ from the third factor, etc... up to finally choosing an $x$ or a $y$ from the $n^{th}$ factor, and then multiplying all of these together.

As such, each of these terms will consist of some number of $x$'s multiplied by some number of $y$'s, where the total number of $x$'s and $y$'s is $n$. For example, choosing $y$ from the first two factors, and $x$ from the rest will produce the term $x^{n-2}y^2$. Alternatively, choosing $x$ from the first $7$ factors and $y$ from the rest results in the term $x^7 y^{n-7}$.

Let's consider a specific example. Consider the terms we see from expanding the following expression (assuming we don't collect any "like terms" along the way):

$$\begin{array}{rcl} (x+y)^4 &=& (x+y)(x+y)(x^2 + xy + xy + y^2)\\\\ &=&(x+y)(x^3 + x^2y + x^2y + xy^2 + x^2y + xy^2 + y^3)\\\\ &=&x^4 + x^3y + x^3y + x^2y^2 +x^3y+x^2y^2 + xy^3 + x^3y + x^2 y^2 + x^2 y^2 + x y^3 + x y^3 + y^4 \end{array}$$

Do you see how every term above takes the form $x^a y^b$ with $a+b=4$?

Now, when we finally "collect like terms", the resulting coefficient on $x^ay^b$ will be the number of times it appears in the expansion. As such, to figure out the coefficient on $x^ay^b$, we just need to figure out how many ways we can form a term that looks like $x^ay^b$.

Consider the terms $xy^3$ above. Note these terms were formed by letting three of the four $(x+y)$ factors contribute a $y$ to the product, with the remaining factor contributing an $x$. As such, the number of these terms will be given by the number of ways we can take $4$ factors and choose $3$ of them to contribute a $y$. In the parlance of the aforementioned combinations, this is given by ${}_4C_3$.

Likewise, the terms $x^2y^2$ were formed by letting $2$ of the $4$ factors contribute a $y$ to the product, with the remaining factors contributing a $x$. Consequently, the number of such terms will be equal to the number of ways we can can take $4$ factors and choose $2$ of them to contribute a $y$. Again, in terms of combinations, this is given by ${}_4C_2$.

In general, we can form terms of the form $x^{n-k}y^k$ by taking $n$ of our factors and choosing $k$ of them to contribute a $y$, which is given in the language of combinations by ${}_nC_k$.

Given that the non-collected terms of the expansion of $(x+y)^n$ can have as few as zero $y$'s or at most $n$ of them (with every integer possibility between), our possible terms are

$$x^n, \quad x^{n-1} y, \quad x^{n-2} y^2, \quad \ldots, \quad x y^{n-1}, \quad y^n$$

Finally, noting that in the expansion of $(x+y)^n$, each $x^{n-k}y^k$ occurs ${}_nC_k$ times, we have: $$(x+y)^n = x^n + {}_nC_1 x^{n-1} y + {}_nC_2 x^{n-2} y^2 + {}_nC_3 x^{n-3} y^3 + \cdots + {}_nC_{n-1} x y^{n-1} + y^n$$ This result would be amazing enough -- but there is more! If we apply the formula for ${}_n C_k$ to compute ${}_n C_i$ and ${}_n C_{i+1}$, we will find they have all but two factors in common.

As such, we can generate each coefficient in the expansion of $(x+y)^n$ from the last.

Let us illustrate this by an example. Suppose we wish to generate the coefficients corresponding to the expansion of $(x+y)^6$. We know it must begin with a $1$, so we write that down.

$$1$$ Then, we multiply this value by the fraction $\frac{n}{1}$. The product gives the coefficient of the second term -- the one corresponding to $x^{n-1}y$. Since in this example, $n=6$, we have: $$1 \times \frac{6}{1} = 6$$ We create a new fraction by decreasing the numerator by 1 and increasing the denominator by 1. The product of this new fraction and our previous value gives the coefficient of the third term -- the one corresponding to $x^{n-2}y^2$. Here, we find this coefficient to be $$6 \times \frac{5}{2} = 15$$ Continuing in this way, decrementing the numerator, incrementing the denominator, and then multiplying the new fraction by the previous value (until we get a 1) yields the rest of the coefficients: $$\begin{array}{rcl} 15 \times \frac{4}{3} &=& 20\\ 20 \times \frac{3}{4} &=& 15\\ 15 \times \frac{2}{5} &=& 6\\ 6 \times \frac{1}{6} &=& 1\\ \end{array}$$ The sequence of coefficients so produced are: 1, 6, 15, 20, 15, 6, 1. This is, of course, the row of Pascal's triangle that provides the coefficients of $(x+y)^6 = x^6 + 6x^5y + 15x^4y^2 + 20x^3y^3 + 15x^2y^4 + 6xy^5 + y^6$, as seen in the version of the triangle below (one with more rows than previously shown): ### Difference of Squares

Suppose we wish to factor $x^2 - y^2$. There does not appear to be a common monomial factor -- so what can we do?

If we work under the assumption that this can break into two or more factors, one thing we might try is to consider different integer values of $x$ and $y$. If we can find a consistent way to factor the resultant integer value of $x^2-y^2$, this might hint at a way to factor the polynomial itself. With this in mind, consider the following table for some randomly chosen values of $x$ and $y$: $$\begin{array}{|c|c|c|c|} x & y & x^2 - y^2 & \textrm{integer factors}\\\hline 5 & 2 & 21 & 7 \cdot 3\\\hline 7 & 4 & 33 & 11 \cdot 3\\\hline 10 & 3 & 91 & 13 \cdot 7\\\hline 11 & 6 & 85 & 17 \cdot 5\\\hline 27 & 14 & 533 & 41 \cdot 13\\\hline \end{array}$$

Can you guess a formula for the integer factors in terms of the values of $x$ and $y$? (Try!)

Note how in the first line above, $7 = 5 + 2$ while $3 = 5 - 2$. Likewise, in the second line, $11 = 7 + 4$ and $3 = 7 -4$. It would appear that one can always factor $x^2 - y^2$ into the product of the sum of $x$ and $y$ and the difference of the same. That is to say, it appears that $$\boxed{\displaystyle{x^2 - y^2 = (x+y)(x-y)}}$$

Expanding the right side quickly verifies this guess is correct:

$$\begin{array}{rcl} (x+y)(x-y) &=& x^2 -xy + xy - y^2\\ &=& x^2 - y^2 \end{array}$$

Of course, now this result serves as a template that helps us factor other polynomial expressions.

Notice for example $16a^2b^6 - 49$ is also a difference of two squares: $(4ab^3)^2$ and $7^2$.   Thus $4ab^3$ plays the role of $x$ and $7$ plays the role of $y$. The analogs of $(x+y)$ and $(x-y)$ then tell us that

$$16a^2b^6 - 49 = (4ab^3 + 7)(4ab^3 - 7)$$

†: OK, you got me -- the values in the table weren't chosen completely at random. They were chosen to make guessing the pattern a bit easier. Note, a polynomial factorization will certainly give us a way to write an integer of that form as a product, but some integers can be written as a product in more than one way. For example, $$7^2 - 3^2 = 40 = 10 \cdot 4 = 20 \cdot 2 = 5 \cdot 8 = 1 \cdot 40$$ For our purposes, all but the first factorization (i.e., $10 \cdot 4$) are essentially distractions. The numbers in the table were chosen so that such "distractions" were minimized.

‡: You may have noticed that we skipped the first step in the expansion of this product where the distributive propery would normally be applied -- which would have given us $x(x-y) + y(x-y)$. Given the number of times one will end up multiplying two binomials together like $(a+b)(c+d)$, we can save ourselves some time in the long run by recognizing we always ends up with the sum of four terms: $$\begin{array}{rcl} (a+b)(c+d) &=& a(c+d) + b(c+d)\\ &=& ac + ad + bc + bd \end{array}$$ To remember how to form these four terms quickly, students often recall the mnemonic FOIL given that the products in question are:

1. $ac$, the product of the two First terms,
2. $ad$, the product of the two Outer terms,
3. $bc$, the product of the two Inner terms, and
4. $bd$, the product of the two Last terms

### Factoring by Grouping & the Strategy of "Hopeful Nibbling"

Let us consider what might go through our mind as we try to factor something like the following: $$xy^2 - 2xy + x - y + 1$$ We might initially be excited to see a common factor of $x$ on the first three terms -- only to be sadly crest-fallen upon realizing the last two terms do not have this common factor!

Still, lets play with those first three terms anyways and see where it leads...

$$xy^2 - 2xy + x - y + 1 = x(y^2 - 2y + 1) - y + 1$$ Aha! There's a recognizable piece in there! Notice that $y^2 - 2y + 1$ fits the form of a perfect square! (the first term is the square of $y$, the last term is the square of $1$, and the middle term is twice the product of these two in magnitude).

Running with this, we can $$\begin{array}{rcl} xy^2 - 2xy + x - y + 1 &=& x(y^2 - 2y + 1) - y + 1\\ &=& x(y-1)^2 - y + 1 \end{array}$$ Of course now, we can now more easily see a connection between the $(y-1)$ factor and the $-y + 1$ sitting on the end. One is almost identical to the other -- except the two signs are wrong.

There's an easy fix -- we just factor out the negative. This reveals a common factor of $(y-1)$ which can be pulled out to yield a successful factorization of our original expression: $$\begin{array}{rcl} xy^2 - 2xy + x - y + 1 &=& x(y-1)^2 - (y-1)\\ &=& (y-1)(x(y-1) - 1)\\ &=& (y-1)(xy - x - 1) \end{array}$$

This strategy of "nibbling" at a piece of the expression where there is something we can try and crossing our fingers hoping that the rest of the problem works out can often be successful. Let's consider another example.

Suppose we wish to factor $x^2 - 2xy + 5x - 10y$. Here, factoring out a common $x$ from the first three terms sadly doesn't lead anywhere: $$x^2 - 2xy + 5x - 10y = x(x-2y + 5) - 10y = ?$$ However, one might also notice that there is a common factor of $5$ in the last two terms. What if we grouped the first two terms together, pulling out their common $x$ -- and grouped the last two terms together, factoring out the aformentioned $5$: $$\begin{array}{rcl} x^2 - 2xy + 5x - 10y &=& (x^2 - 2xy) + (5x - 10y)\\ &=& x(x-2y) + 5(x-2y) \quad \scriptsize{\textrm{How nice was that! There's a common (x-2y) factor!}}\\ &=& (x-2y)(x+5) \end{array}$$

This technique used above of splitting a polynomial into groups of terms, and then identifying a factor common to all of the groups can be helpful in factoring polynomials more generally, as the following two additional examples suggest.

Importantly, though -- don't be afraid to "play" with expression in question.You may have to consider writing an expression in several different ways before something breaks. Not everything will work out beautifully on your first attempt. Be persistant though -- "nibble hopefully" -- and something will eventually crack!

$$\begin{array}{rcl} x^2 + 3x - 3y - y^2 &=& (x^2 - y^2) + (3x - 3y) \quad \scriptsize{\textrm{notice we had to move some terms around}}\\ &=& (x+y)(x-y) + 3(x-y)\\ &=& (x-y)(x+y+3)\\\\ a^2b + 2a^2c + ab + 2ac + b + 2c&=& (a^2b + ab + b) + (2a^2c + 2ac + 2c) \quad \scriptsize{\textrm{again we moved some terms around}}\\ &=& b(a^2 + a + 1) + 2c(a^2 + a + 1)\\ &=& (a^2 + a + 1)(b + 2c) \end{array}$$
With a clever addition of zero, we can even apply this strategy to factor a difference of squares as already addressed in the last secton: $$\begin{array}{rcl} x^2 - y^2 &=& x^2 + \overbrace{xy - xy}^{zero} - y^2\\ &=& (x^2 + xy) + (-xy - y^2) \quad \scriptsize{\textrm{grouping the first two and last two terms}}\\ &=& x(x+y) + (-y)(x+y) \quad \scriptsize{\textrm{after factoring each group}}\\ &=& (x+y)(x + (-y)) \quad \scriptsize{\textrm{the common } (x+y) \textrm{ is factored out}}\\ &=& (x+y)(x-y) \end{array}$$

### Sums and Differences of Cubes

We know how to factor the difference of squares now -- so how about the difference of cubes?

Taking a cue from how adding a well-chosen value of zero helped us factor the former by grouping, let us apply a similar strategy to the latter.:

$$\begin{array}{rcl} x^3 - y^3 &=& x^3 + \overbrace{-x^2y + x^2y}^{\textrm{zero}} - y^3\\ &=& (x^3 - x^2y) + (x^2y - y^3)\\ &=& x^2(x-y) + y(x^2-y^2)\\ &=& x^2(x-y) + y(x+y)(x-y)\\ &=& (x-y)(x^2 + y(x+y))\\ &=& (x-y)(x^2 + xy + y^2) \end{array}$$

The sum of cubes can be factored using a very similar process, giving us in total two new factorization rules:

$$\boxed{\displaystyle{\begin{array}{rcl} x^3 - y^3 &=& (x - y)(x^2 + xy + y^2)\\ x^3 + y^3 &=& (x + y)(x^2 - xy + y^2) \end{array}}}$$

Just as before, the above gives us two more templates for factoring other polynomials. For example, if one was attempting to factor $a^3b^6 + 8$, one might notice that the first term is the cube of $ab^2$ and the second is the cube of $2$. Using these values in the above rules as our $x$ and $y$ respectively, we discover

$$\begin{array}{rcl} a^3b^6+8 &=& (ab^2)^3 + 2^3\\ &=& (ab^2 + 2)((ab^2)^2 - (ab^2)\cdot 2 + 2^2)\\ &=& (ab^2 + 2)(a^2b^4 - 2ab^2 + 4) \end{array}$$

### Factoring Trinomials

Factoring a trinomial that is not the square of a binomial and whose terms don't have a common monomial factor requires a bit of detective work.

Suppose we wish to factor a trinomial of the form $x^2 + bx + c$, where $b$ and $c$ are integers. Let us make a guess that $x^2 + bx + c = (x + r)(x + s)$. Expanding we see $x^2 + bx + c = x^2 + (r + s)x + r \cdot s$. As such, we seek values of $r$ and $s$ so that $r+s = b$ and $r \cdot s = c$.

Let us illustrate how we might find these values of $r$ and $s$ with an example:

Suppose we want to factor $x^2 - 5x + 6$. Thus, we need $r$ and $s$ so that $r+s = -5$ and $r \cdot s = 6$. Given that $r \cdot s$ must be positive, we notice $r$ and $s$ must have the same sign.

Now consider possible integer factorizations of $6$, namely:

$$\begin{array}{rcr} 1 &\times& 6\\ -1 &\times& -6\\ 2 &\times& 3\\ -2 &\times& -3 \end{array}$$

When one adds two numbers of the same sign, one adds their magnitudes and keeps the same sign on the result. Ergo, $r$ and $s$ must be given by a product where the magnitudes of the numbers involved sum to $5$. Thus, the magnitudes involved must be $2$ and $3$.

Given that $r+s = -5$ and $r$ and $s$ have the same sign, we further conclude $r$ and $s$ must both be negative. As such, we make a guess $r = -2$ and $s = -3$. Expanding $(x-2)(x-3)$ confirms this guess is correct:

$$\begin{array}{rcl} (x-2)(x-3) &=& x^2 -3x -2x + 6\\ &=& x^2 - 5x + 6 \end{array}$$

Now suppose we wish to factor a trinomial whose leading coefficient is not equal to one -- something of the form $ax^2 + bx + c$. Things are a bit more complicated here. One way to proceed would be to first make a guess that the factorization takes the form $(px + r)(qx + s)$. Expanding this product, we notice

$$\begin{array}{rcl} (px+r)(qx+s) &=& pqx^2 + psx + qrx + rs\\ &=& pqx^2 + (ps + qr)x + rs \end{array}$$

Thus, $ax^2 + bx + c = pqx^2 + (ps + qr)x + rs$. Notice that the product of the leading coefficient and the constant term is given by both $ac$ and $pqrs$. The product of the two values in the parentheses is also $pqrs$. As such, we seek two values, $pq$ and $rs$ whose product is $ac$ and whose sum is $b$.

Let us demonstrate the rest of the technique with an example...

Suppose we wish to factor $2x^2 + 7x + 6$. We then seek two values $pq$ and $rs$ whose product is $12$ and whose sum is $7$. The only integer possibilities are, of course, $3$ and $4$. This gives us enough information to finish the factorization by grouping: $$\begin{array}{rcl} 2x^2 + 7x + 6 &=& 2x^2 + (4x + 3x) + 6\\ &=& (2x^2 + 4x) + (3x + 6)\\ &=& 2x(x+2) + 3(x+2)\\ &=& (2x+3)(x+2) \end{array}$$

### Irreducible Polynomials

The above spends a good bit of effort detailing some tricks for factoring polynomials -- but is it possible for a polynomial to not be able to be factored any further? ...and how would we know that is the case?

We should be careful about expressing exactly what we mean here. As a matter of verbiage, we say the degree of a polynomial of one variable is the highest exponent seen on the variable in question in the polynomial. So for example, $x^2 + 3x - 5$ has degree 2, while $2x^3 - x + 7$ has degree $3$.

As an unrelated side note, the degree of a term in a polynomial of one variable is the exponent on the variable seen in that term. Also, the traditional way to write a polynomial (unless there is an advantage in doing something else) is to order the terms of the polynomial in descending order by the degree of the terms involved -- much like the digits of the related base $x$ integer.

Let us call a polynomial with integer coefficients irreducible when it can't be factored into a product of two other polynomials with integer coefficients each of a lesser degree.

So expressing things more clearly, we are curious if it is possible a polynomial can be irreducible and how can we tell when that is the case?

The answer to the first question is a resounding yes. For example, trying to factor $x^2+x+1$ into $(x+r)(x+s)$ where $r$ and $s$ are integers, as described in the last section, quickly leads nowhere. Gotthold Eisenstein The answer to the second question however, is more complicated. The following result, named after the German mathematician Gotthold Eisenstein gives us a partial answer:

 Eisenstein's Criterion: A polynomial $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0$ with integer coefficients is irreducible when there is a prime $p$ where: $p$ divides evenly into every $a_i$ except $a_n$ $p^2$ does not divide $a_0$ evenly

Sadly, this is only a sufficient and not a necessary condition for a polynomial to be irreducible. That means that Eisenstein's criterion not holding does not guarantee the polynomial can be factored into the product of two polynomials each of lesser degree. Still, its better than nothing.

Let's see how it works...

Suppose a polynomial $a_n x^n + a_{n-1} + \cdots + a_2 x^2 + a_1 x + a_0$ that satisfied Eisenstein's criterion could be factored into two polynomials of lesser degree. (Our aim is of course to show such an assumption leads to some contradiction, and thus this can't every actually happen.). In particular, let us assume that $$a_n x^n + a_{n-1} + \cdots + a_2 x^2 + a_1 x + a_0 = (c_r x^r + c_{r-1} x^{r-1} + \cdots + c_0)(d_s x^s + d_{s-1} x^{s-1} + \cdots + d_0)$$ Note it must be the case that $a_0 = c_0 d_0$. So if $a_0$ is evenly divisible by $p$, but not $p^2$, one of $c_0$ and $d_0$ must be evenly divisible by $p$, but not both. Without loss of generality, let us assume $p$ divides $c_0$ evenly but not $d_0$.

It must also be the case that $a_n = c_r d_s$. Given that $p$ does not evenly divide $a_n$, it can neither divide $c_r$ nor $d_s$.

Now, note that $a_1 = c_0 d_1 + c_1 d_0$. As $p$ divides $a_1$ and $c_0$, but not $d_0$, it must be that $p$ divides $c_1$.

Likewise, note that $a_2 = c_0 d_2 + c_1 d_1 + c_2 d_0$. As $p$ divides $a_2$, $c_0$, and $c_1$, but not $d_0$, it must be that $p$ divides $c_2$.

Similarly, note that $a_3 = c_0 d_3 + c_1 d_2 + c_2 d_1 + c_3 d_0$. As $p$ divides $a_3$, $c_0$, $c_1$, and $c_2$, but not $d_0$, it must be that $p$ divides $c_3$.

We can continue in this way to establish that $p$ divides $c_4, c_5, c_6, \ldots$ up to $c_r$. However, this last conclusion that $p$ divides $c_r$ is a problem! Recall, we earlier concluded that $p$ didn't divide $c_r$ evenly! We have found our contradiction.

Thus, if Eisenstein's criterion holds, no such polynomials of lesser degree exist, and $a_n x^n + a_{n-1} + \cdots + a_2 x^2 + a_1 x + a_0$ is irreducible.

As an example of how to use Eisenstein's criterion, consider the polynomial $3x^4 + 15x^2 + 10$. Note that the prime $p=5$ evenly divides the last two coefficients, but not the first, and $p^2 = 25$ does not divide the last coefficient. Thus, this polynomial is irreducible and can't be factored into the product of smaller degree polynomials.

As an interesting piece of trivia, at the young age of twenty Eisenstein met the great mathematician William Rowan Hamilton in Dublin, who gave him a copy of his book on Niels Henrik Abel's famed impossibility theorem. Stay tuned, we will have much more to say about this really important theorem later!