Irreducible Polynomials

A nonconstant polynomial \(f(x) \in F[x]\) is irreducible over a field \(F\) if \(f(x)\) cannot be expressed as a product of two polynomials \(g(x)\) and \(h(x)\) in \(F[x]\), where the degrees of \(g(x)\) and \(h(x)\) are both smaller than the degree of \(f(x)\). Irreducible polynomials function as the prime numbers of polynomial rings.

Example

The polynomial \(x^2 - 2 \in {\mathbb Q}[x]\) is irreducible since it cannot be factored any further over the rational numbers. Similarly, \(x^2 + 1\) is irreducible over the real numbers.

Example

The polynomial \(p(x) = x^3 + x^2 + 2\) is irreducible over \({\mathbb Z}_3[x]\). Suppose that this polynomial was reducible over \({\mathbb Z}_3[x]\). By the division algorithm there would have to be a factor of the form \(x - a\), where \(a\) is some element in \({\mathbb Z}_3[x]\). Hence, it would have to be true that \(p(a) = 0\). However, \[\begin{aligned}p(0) & = 2 \\ p(1) & = 1 \\ p(2) & = 2\end{aligned}\]. Therefore, \(p(x)\) has no zeros in \({\mathbb Z}_3\) and must be irreducible.

Lemma

Let \(p(x) \in {\mathbb Q}[x]\). Then \[\begin{aligned}\end{aligned}\], where \(r, s, a_0, \ldots, a_n\) are integers, the \(a_i\)'s are relatively prime, and \(r\) and \(s\) are relatively prime.

Proof

Suppose that \[\begin{aligned}\end{aligned}\], where the \(b_i\)'s and the \(c_i\)'s are integers. We can rewrite \(p(x)\) as \[\begin{aligned}\end{aligned}\], where \(d_0, \ldots, d_n\) are integers. Let \(d\) be the greatest common divisor of \(d_0, \ldots, d_n\). Then \[\begin{aligned}\end{aligned}\], where \(d_i = d a_i\) and the \(a_i\)'s are relatively prime. Reducing \(d /(c_0 \cdots c_n)\) to its lowest terms, we can write \[\begin{aligned}\end{aligned}\], where \(\gcd(r,s) = 1\).

Theorem: Gauss's Lemma

Let \(p(x) \in {\mathbb Z}[x]\) be a monic polynomial such that \(p(x)\) factors into a product of two polynomials \(\alpha(x)\) and \(\beta(x)\) in \({\mathbb Q}[x]\), where the degrees of both \(\alpha(x)\) and \(\beta(x)\) are less than the degree of \(p(x)\). Then \(p(x) = a(x) b(x)\), where \(a(x)\) and \(b(x)\) are monic polynomials in \({\mathbb Z}[x]\) with \(\deg \alpha(x) = \deg a(x)\) and \(\deg \beta(x) = \deg b(x)\).

Proof

By , we can assume that \[\begin{aligned}\alpha(x) & = \frac{c_1}{d_1} (a_0 + a_1 x + \cdots + a_m x^m ) = \frac{c_1}{d_1} \alpha_1(x) \\ \beta(x) & = \frac{c_2}{d_2} (b_0 + b_1 x + \cdots + b_n x^n) = \frac{c_2}{d_2} \beta_1(x)\end{aligned}\], where the \(a_i\)'s are relatively prime and the \(b_i\)'s are relatively prime. Consequently, \[\begin{aligned}\end{aligned}\], where \(c/d\) is the product of \(c_1/d_1\) and \(c_2/d_2\) expressed in lowest terms. Hence, \(d p(x) = c \alpha_1(x) \beta_1(x)\).

If \(d = 1\), then \(c a_m b_n = 1\) since \(p(x)\) is a monic polynomial. Hence, either \(c=1\) or \(c = -1\). If \(c = 1\), then either \(a_m = b_n = 1\) or \(a_m = b_n = -1\). In the first case \(p(x) = \alpha_1(x) \beta_1(x)\), where \(\alpha_1(x)\) and \(\beta_1(x)\) are monic polynomials with \(\deg \alpha(x) = \deg \alpha_1(x)\) and \(\deg \beta(x) = \deg \beta_1(x)\). In the second case \(a(x) = -\alpha_1(x)\) and \(b(x) = -\beta_1(x)\) are the correct monic polynomials since \(p(x) = (-\alpha_1(x))(- \beta_1(x)) = a(x) b(x)\). The case in which \(c = -1\) can be handled similarly.

Now suppose that \(d \neq 1\). Since \(\gcd(c, d) = 1\), there exists a prime \(p\) such that \(p \mid d\) and \(p \notdivide c\). Also, since the coefficients of \(\alpha_1(x)\) are relatively prime, there exists a coefficient \(a_i\) such that \(p \notdivide a_i\). Similarly, there exists a coefficient \(b_j\) of \(\beta_1(x)\) such that \(p \notdivide b_j\). Let \(\alpha_1'(x)\) and \(\beta_1'(x)\) be the polynomials in \({\mathbb Z}_p[x]\) obtained by reducing the coefficients of \(\alpha_1(x)\) and \(\beta_1(x)\) modulo \(p\). Since \(p \mid d\), \(\alpha_1'(x) \beta_1'(x) = 0\) in \({\mathbb Z}_p[x]\). However, this is impossible since neither \(\alpha_1'(x)\) nor \(\beta_1'(x)\) is the zero polynomial and \({\mathbb Z}_p[x]\) is an integral domain. Therefore, \(d=1\) and the theorem is proven.

Example

Let \(p(x) = x^4 - 2 x^3 + x + 1\). We shall show that \(p(x)\) is irreducible over \({\mathbb Q}[x]\). Assume that \(p(x)\) is reducible. Then either \(p(x)\) has a linear factor, say \(p(x) = (x - \alpha) q(x)\), where \(q(x)\) is a polynomial of degree three, or \(p(x)\) has two quadratic factors.

If \(p(x)\) has a linear factor in \({\mathbb Q}[x]\), then it has a zero in \({\mathbb Z}\). By , any zero must divide 1 and therefore must be \(\pm 1\); however, \(p(1) = 1\) and \(p(-1)= 3\). Consequently, we have eliminated the possibility that \(p(x)\) has any linear factors.

Therefore, if \(p(x)\) is reducible it must factor into two quadratic polynomials, say \[\begin{aligned}p(x) & = (x^2 + ax + b )( x^2 + cx + d ) \\ & = x^4 + (a + c)x^3 + (ac + b + d)x^2 + (ad + bc)x + bd\end{aligned}\], where each factor is in \({\mathbb Z}[x]\) by Gauss's Lemma. Hence, \[\begin{aligned}a + c & = - 2 \\ ac + b + d & = 0 \\ ad + bc & = 1 \\ bd & = 1\end{aligned}\]. Since \(bd = 1\), either \(b = d = 1\) or \(b = d = -1\). In either case \(b = d\) and so \[\begin{aligned}\end{aligned}\]. Since \(a + c = -2\), we know that \(-2b = 1\). This is impossible since \(b\) is an integer. Therefore, \(p(x)\) must be irreducible over \({\mathbb Q}\).

Theorem: Eisenstein's Criterion

Let \(p\) be a prime and suppose that \[\begin{aligned}\end{aligned}\]. If \(p \mid a_i\) for \(i = 0, 1, \ldots, n-1\), but \(p \notdivide a_n\) and \(p^2 \notdivide a_0\), then \(f(x)\) is irreducible over \({\mathbb Q}\).

Proof

By Gauss's Lemma (see and ), we need only show that \(f(x)\) does not factor into polynomials of lower degree in \({\mathbb Z}[x]\). Let \[\begin{aligned}\end{aligned}\] be a factorization in \({\mathbb Z}[x]\), with \(b_r\) and \(c_s\) not equal to zero and \(r, s \lt n\). Since \(p^2\) does not divide \(a_0 = b_0 c_0\), either \(b_0\) or \(c_0\) is not divisible by \(p\). Suppose that \(p \notdivide b_0\) and \(p \mid c_0\). Since \(p \notdivide a_n\) and \(a_n = b_r c_s\), neither \(b_r\) nor \(c_s\) is divisible by \(p\). Let \(m\) be the smallest value of \(k\) such that \(p \notdivide c_k\). Then \[\begin{aligned}\end{aligned}\] is not divisible by \(p\), since each term on the right-hand side of the equation is divisible by \(p\) except for \(b_0 c_m\). Therefore, \(m = n\) since \(a_i\) is divisible by \(p\) for \(m \lt n\). Hence, \(f(x)\) cannot be factored into polynomials of lower degree and therefore must be irreducible.

Example

The polynomial \[\begin{aligned}\end{aligned}\] is easily seen to be irreducible over \({\mathbb Q}\) by Eisenstein's Criterion if we let \(p = 3\).

Eisenstein's Criterion is more useful in constructing irreducible polynomials of a certain degree over \({\mathbb Q}\) than in determining the irreducibility of an arbitrary polynomial in \({\mathbb Q}[x]\): given an arbitrary polynomial, it is not very likely that we can apply Eisenstein's Criterion. The real value of is that we now have an easy method of generating irreducible polynomials of any degree.

Ideals in F\lbrack x \rbrack

Let \(F\) be a field. Recall that a principal ideal in \(F[x]\) is an ideal \(\langle p(x) \rangle\) generated by some polynomial \(p(x)\); that is, \[\begin{aligned}\end{aligned}\].

Example

The polynomial \(x^2\) in \(F[x]\) generates the ideal \(\langle x^2 \rangle\) consisting of all polynomials with no constant term or term of degree \(1\).

Theorem

If \(F\) is a field, then every ideal in \(F[x]\) is a principal ideal.

Proof

Let \(I\) be an ideal of \(F[x]\). If \(I\) is the zero ideal, the theorem is easily true. Suppose that \(I\) is a nontrivial ideal in \(F[x]\), and let \(p(x) \in I\) be a nonzero element of minimal degree. If \(\deg p(x)= 0\), then \(p(x)\) is a nonzero constant and 1 must be in \(I\). Since 1 generates all of \(F[x]\), \(\langle 1 \rangle = I = F[x]\) and \(I\) is again a principal ideal.

Now assume that \(\deg p(x) \geq 1\) and let \(f(x)\) be any element in \(I\). By the division algorithm there exist \(q(x)\) and \(r(x)\) in \(F[x]\) such that \(f(x) = p(x) q(x) + r(x)\) and \(\deg r(x) \lt \deg p(x)\). Since \(f(x), p(x) \in I\) and \(I\) is an ideal, \(r(x) = f(x) - p(x) q(x)\) is also in \(I\). However, since we chose \(p(x)\) to be of minimal degree, \(r(x)\) must be the zero polynomial. Since we can write any element \(f(x)\) in \(I\) as \(p(x) q(x)\) for some \(q(x) \in F[x]\), it must be the case that \(I = \langle p(x) \rangle\).

Example

It is not the case that every ideal in the ring \(F[x,y]\) is a principal ideal. Consider the ideal of \(F[x, y]\) generated by the polynomials \(x\) and \(y\). This is the ideal of \(F[x, y]\) consisting of all polynomials with no constant term. Since both \(x\) and \(y\) are in the ideal, no single polynomial can generate the entire ideal.

Polynomial rings are very important for computational approaches to algebra, and so Sage makes it very easy to compute with polynomials, over rings, or over fields. And it is trivial to check if a polynomial is irreducible.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

Historical Note

Throughout history, the solution of polynomial equations has been a challenging problem. The Babylonians knew how to solve the equation \(ax^2 + bx + c = 0\). Omar Khayyam (10481131) devised methods of solving cubic equations through the use of geometric constructions and conic sections. The algebraic solution of the general cubic equation \(ax^3 + bx^2 + cx + d = 0\) was not discovered until the sixteenth century. An Italian mathematician, Luca Pacioli (ca. 14451509), wrote in Summa de Arithmetica that the solution of the cubic was impossible. This was taken as a challenge by the rest of the mathematical community.

Scipione del Ferro (14651526), of the University of Bologna, solved the depressed cubic, \[\begin{aligned}\end{aligned}\]. He kept his solution an absolute secret. This may seem surprising today, when mathematicians are usually very eager to publish their results, but in the days of the Italian Renaissance secrecy was customary. Academic appointments were not easy to secure and depended on the ability to prevail in public contests. Such challenges could be issued at any time. Consequently, any major new discovery was a valuable weapon in such a contest. If an opponent presented a list of problems to be solved, del Ferro could in turn present a list of depressed cubics. He kept the secret of his discovery throughout his life, passing it on only on his deathbed to his student Antonio Fior (ca. 1506?).

Although Fior was not the equal of his teacher, he immediately issued a challenge to Niccolo Fontana (14991557). Fontana was known as Tartaglia (the Stammerer). As a youth he had suffered a blow from the sword of a French soldier during an attack on his village. He survived the savage wound, but his speech was permanently impaired. Tartaglia sent Fior a list of 30 various mathematical problems; Fior countered by sending Tartaglia a list of 30 depressed cubics. Tartaglia would either solve all 30 of the problems or absolutely fail. After much effort Tartaglia finally succeeded in solving the depressed cubic and defeated Fior, who faded into obscurity.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

Symbols used here

a \mid b,\ \gcd(a,b)

divides, greatest common divisor
b is a multiple of a; the largest number dividing both.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

i

imaginary unit
i² = −1.

\pm

plus or minus
Both signs at once: x = 3 ± 2 means 5 and 1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\neq

not equal
The two sides are different.

\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}

number sets
Naturals, integers, rationals, reals, complex numbers.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

(G, \cdot),\ e,\ g^{-1}

group, identity, inverse
A set with an operation; the do-nothing element; the element that undoes g.

G \cong H,\ G / N

isomorphic, quotient group
Same structure; the group of cosets of a normal subgroup N.

\mathbb{Z}/n\mathbb{Z},\ \mathbb{Z}_n

integers modulo n
The remainders 0…n−1 with clock arithmetic.

\operatorname{Hom}(A, B),\ f \circ g

arrows from A to B, composition
The set of morphisms; do g then f.

Questions people ask

What is a group, in plain words?

A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group — that is where the idea came from.

What is the difference between a ring and a field?

A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.

Irreducible Polynomials