Section 5.4 Irreducibility Criteria
Lemma 5.15.
Let \(p(x) \in {\mathbb Q}[x]\text{.}\) Then
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
where the \(b_i\)'s and the \(c_i\)'s are integers. We can rewrite \(p(x)\) as
where \(d_0, \ldots, d_n\) are integers. Let \(d\) be the greatest common divisor of \(d_0, \ldots, d_n\text{.}\) Then
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
where \(\gcd(r,s) = 1\text{.}\)
Theorem 5.16. 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]\text{,}\) where the degrees of both \(\alpha(x)\) and \(\beta(x)\) are less than the degree of \(p(x)\text{.}\) Then \(p(x) = a(x) b(x)\text{,}\) 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)\text{.}\)
Proof.
By Lemma 5.15, we can assume that
where the \(a_i\)'s are relatively prime and the \(b_i\)'s are relatively prime. Consequently,
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)\text{.}\)
If \(d = 1\text{,}\) then \(c a_m b_n = 1\) since \(p(x)\) is a monic polynomial. Hence, either \(c=1\) or \(c = -1\text{.}\) If \(c = 1\text{,}\) then either \(a_m = b_n = 1\) or \(a_m = b_n = -1\text{.}\) In the first case \(p(x) = \alpha_1(x) \beta_1(x)\text{,}\) 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)\text{.}\) 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)\text{.}\) The case in which \(c = -1\) can be handled similarly.
Now suppose that \(d \neq 1\text{.}\) Since \(\gcd(c, d) = 1\text{,}\) there exists a prime \(p\) such that \(p \mid d\) and \(p \notdivide c\text{.}\) Also, since the coefficients of \(\alpha_1(x)\) are relatively prime, there exists a coefficient \(a_i\) such that \(p \notdivide a_i\text{.}\) Similarly, there exists a coefficient \(b_j\) of \(\beta_1(x)\) such that \(p \notdivide b_j\text{.}\) 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\text{.}\) Since \(p \mid d\text{,}\) \(\alpha_1'(x) \beta_1'(x) = 0\) in \({\mathbb Z}_p[x]\text{.}\) 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.
Corollary 5.17.
Let \(p(x) = x^n + a_{n - 1} x^{n - 1} + \cdots + a_0\) be a polynomial with coefficients in \({\mathbb Z}\) and \(a_0 \neq 0\text{.}\) If \(p(x)\) has a zero in \({\mathbb Q}\text{,}\) then \(p(x)\) also has a zero \(\alpha\) in \({\mathbb Z}\text{.}\) Furthermore, \(\alpha\) divides \(a_0\text{.}\)
Proof.
Let \(p(x)\) have a zero \(a \in {\mathbb Q}\text{.}\) Then \(p(x)\) must have a linear factor \(x - a\text{.}\) By Gauss's Lemma, \(p(x)\) has a factorization with a linear factor in \({\mathbb Z}[x]\text{.}\) Hence, for some \(\alpha \in {\mathbb Z}\)
Thus \(a_0 /\alpha \in {\mathbb Z}\) and so \(\alpha \mid a_0\text{.}\)
Corollary 5.18.
Let \(p(x) = x^n + a_{n-1} x^{n-1} + \cdots + a_0\) be a polynomial of degree \(n=2\) or \(3\) with coeficients in \(\mathbb Z\text{.}\) If \(a_0 \neq 0\) and \(\alpha\) is not a zero of \(p(x)\) for all integers \(\alpha\) dividing \(a_0\text{,}\) then \(p(x)\) is irreducible.
Proof.
Suppose that \(p(x)\) factors into non-constant polynomials. Because \(p(x)\) has degree \(2\) or \(3\text{,}\) one of the factors must be linear and so \(p(x)\) has a zero. By Corollary 5.17, this zero is an integer dividing \(a_0\text{,}\) which contradicts our assumption.
Corollary 5.18 gives a way to completely determine whether a monic polynomial \(p(x)\) of degree \(2\) or \(3\) is irreducible. There are only finitely many integer divisors of the constant term of \(p(x)\text{.}\) If one of these divisors is a zero of \(p(x)\text{,}\) then it has a linear factor and is not irreducible. If none of them are zeros, then \(p(x)\) is irreducible by Corollary 5.18.
Example 5.19.
Let \(p(x) = x^3 - 2x + 3\text{.}\) By Corollary 5.18, in order to tell if \(p(x)\) is irreducible, we check whether any of the integer divisors of the constant term \(3\) are zeros of \(p(x)\text{:}\)
Since none of these divisors are zeros of \(p(x)\text{,}\) it is an irreducible polynomial.
Example 5.20.
Let \(p(x) = x^4 - 2 x^3 + x + 1\text{.}\) We shall show that \(p(x)\) is irreducible over \({\mathbb Q}[x]\text{.}\) Assume that \(p(x)\) is reducible. Then either \(p(x)\) has a linear factor, say \(p(x) = (x - \alpha) q(x)\text{,}\) 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]\text{,}\) then it has a zero in \({\mathbb Z}\text{.}\) By Corollary 5.17, any zero must divide 1 and therefore must be \(\pm 1\text{;}\) however, \(p(1) = 1\) and \(p(-1)= 3\text{.}\) 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
where each factor is in \({\mathbb Z}[x]\) by Gauss's Lemma. Hence,
Since \(bd = 1\text{,}\) either \(b = d = 1\) or \(b = d = -1\text{.}\) In either case \(b = d\) and so
Since \(a + c = -2\text{,}\) we know that \(-2b = 1\text{.}\) This is impossible since \(b\) is an integer. Therefore, \(p(x)\) must be irreducible over \({\mathbb Q}\text{.}\)
Theorem 5.21. Eisenstein's Criterion.
Let \(p\) be a prime and suppose that
If \(p \mid a_i\) for \(i = 0, 1, \ldots, n-1\text{,}\) but \(p \notdivide a_n\) and \(p^2 \notdivide a_0\text{,}\) then \(f(x)\) is irreducible over \({\mathbb Q}\text{.}\)
Proof.
By Gauss's Lemma, we need only show that \(f(x)\) does not factor into polynomials of lower degree in \({\mathbb Z}[x]\text{.}\) Let
be a factorization in \({\mathbb Z}[x]\text{,}\) with \(b_r\) and \(c_s\) not equal to zero and \(r, s \lt n\text{.}\) Since \(p^2\) does not divide \(a_0 = b_0 c_0\text{,}\) either \(b_0\) or \(c_0\) is not divisible by \(p\text{.}\) Suppose that \(p \notdivide b_0\) and \(p \mid c_0\text{.}\) Since \(p \notdivide a_n\) and \(a_n = b_r c_s\text{,}\) neither \(b_r\) nor \(c_s\) is divisible by \(p\text{.}\) Let \(m\) be the smallest value of \(k\) such that \(p \notdivide c_k\text{.}\) Then
is not divisible by \(p\text{,}\) since each term on the right-hand side of the equation is divisible by \(p\) except for \(b_0 c_m\text{.}\) Therefore, \(m = n\) since \(a_i\) is divisible by \(p\) for \(m \lt n\text{.}\) Hence, \(f(x)\) cannot be factored into polynomials of lower degree and therefore must be irreducible.
Example 5.22.
The polynomial
is easily seen to be irreducible over \({\mathbb Q}\) by Eisenstein's Criterion if we let \(p = 3\text{.}\)
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]\text{:}\) given an arbitrary polynomial, it is not very likely that we can apply Eisenstein's Criterion. The real value of Theorem 5.21 is that we now have an easy method of generating irreducible polynomials of any degree.
Our final irreducibility criterion uses modular arithmetic. In Example 4.19, we saw the homomorphism \(\phi_p\colon \mathbb Z \rightarrow \mathbb Z_p\) taking the equivalence class modulo \(p\text{.}\) Here, we take \(p\) to be a prime. In addition, there is a homomorphism \(\psi_p\colon \mathbb Z[x] \rightarrow \mathbb Z_p[x]\) by taking the equivalence class of each coefficient of the polynomial. Our next theorem uses this reduction homomorphism.
Theorem 5.23.
Let \(f(x) = a_n x^n + \cdots + a_0\) be an integer polynomial. Let \(p\) be a prime. If \(p\) does not divide \(a_n\) and the polynomial \(\psi_p(f)\) is irreducible in \(\mathbb Z_p[x]\text{,}\) then \(f(x)\) is irreducible in \(\mathbb Q[x]\text{.}\)
Proof.
We prove the contrapositive. Suppose that \(f(x)\) factors into two polynomials as
where \(r, s > 0\text{.}\) By Theorem 5.16, we can assume that the coefficients \(b_r, \cdots, b_0, c_s, \cdots, c_0\) are all integers. Then applying the modulo \(p\) homomorphism,
Since \(p\) does not divide the leading coefficient \(a_n = b_r c_s\text{,}\) then it does not divide the leading coefficients \(b_r\) or \(c_s\text{.}\) Therefore, \(\phi_p(b_r) x^r + \cdots + \phi_p(b_0)\) and \(\phi_p(c_s) x^s + \cdots + \phi_p(c_0)\) are non-constant polynomials. Thus, \(\psi_p(f)\) is not irreducible in \(\mathbb Z_p[x]\text{.}\)
Theorem 5.23 gives a criterion for irreducibility of integer polynomials, but it isn't much use unless we know how to prove that a polynomial in \(\mathbb Z_p[x]\) is irreducible. However, there are only finitely many polynomials in \(\mathbb Z_p[x]\) of a given degree, so we can just do trial division by all of them.
Example 5.24.
Let \(f(x) = x^4 + 2x^3 - 2x^2 + 3x - 7\text{.}\) Modulo \(p=2\text{,}\) \(\psi_2(f) = x^4 + x + 1\text{.}\) If \(\psi_2(f)\) factors into non-constant polynomials, then at least one of those factors has degree \(2\) or less. But, \(\psi_2(f)\) doesn't have a linear factor because \(0\) and \(1\) are not zeros. We next need to try degree 2 polynomials, and of these only the irreducible ones. There are \(4\) monic degree 2 polynomials in \(\mathbb Z_2[x]\text{.}\) Of these, two have \(x\) as a factor: \(x^2\) and \(x^2+x\text{.}\) A third has \(1\) as a zero: \(x^2+1\text{.}\) Therefore, \(x^2+x+1\) is the only degree 2 irreducible polynomial in \(\mathbb Z_2[x]\text{.}\) We can divide \(\psi_2(f)\) by \(x^2+x+1\) with remainder to get:
Therefore, \(\psi_2(f)\) is not divisible by \(x^2+x+1\) and so irreducible.
In Example 5.24, we showed that \(x^4 + x + 1\) is an irreducible polynomial in \(\mathbb Z_2[x]\text{.}\) If we had any other integer polynomial \(g\) which was congruent to \(x^4 + x + 1\) modulo 2, then we would also know that \(g\) was irreducible. For this reason, it is useful to know the irreducible polynomials in finite fields. Here is a complete list of the irreducible polynomials in \(\mathbb Z_2[x]\) up to degree \(4\text{,}\) which can easily be confirmed by checking for zeros and using trial division, as in Example 5.24: