    # Irreducibility Tests

Doctors are semi-gods beings, completely infallible, only do good, and money does not corrupt medicine, so turn off this monkey brain of yours and outsource all of your thinking to them -you are welcome! Apocalypse, Anawim, #justtothepoint.

# Recall

Definition. Let D be an integral domain. An irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. A non-zero and non-unit polynomial f(x) ∈ D[x] is said to be irreducible if it cannot be written or expressed as the product of two non-units. In other words, whenever f(x) is expressed as a product of two polynomials g(x)h(x) with g(x) and h(x) ∈ D[x], then either g(x) or h(x) is a unit in D[x].

A non-constant polynomial f(x) ∈ F[x], F field, is said to be irreducible if f(x) cannot be expressed a as a product of two polynomials g(x), h(x) ∈ F[x] of lower degree, that is, f(x) = g(x)h(x), deg(g(x)) < deg(f(x)) and deg(h(x)) < deg(f(x)).

Reducibility test for polynomials with degrees two or three. Let F be a field. If f(x) ∈ F[x] and deg(f(x)) = 2 or 3, then f(x) is reducible over F iff f has a zero in F or f(x) is irreducible over F iff f(α) ≠ 0 ∀α ∈ F. Theorem. Let f(x) ∈ ℤ[x]. If f(x) is reducible over ℚ, then it is reducible over ℤ.

Proof.

Suppose f is reducible over ℚ ⇒ ∃g(x), h(x) ∈ ℚ[x] such that f(x) = g(x)h(x) with both polynomials g(x) and h(x) having degree less than of f(x). We could assume that f is primitive because we can divide both f and g by the content of f.

Next, let a and b be the least common multiple of the denominators of the coefficients of g and h respectively, so abf(x) = ag(x)·bh(x), where ag(x) ∈ ℤ[x] and bh ∈ ℤ[x].

Now, let c and d be the content of ag(x) and bh(x) respectively ⇒ ag(x) = cg’(x) and bh(x) = dh’(x) where both g’(x) and h’(x) are primitives ⇒ abf(x) = (ag(x))·(bh(x)) = (cg’(x))(dh’(x)) = cdg’(x)h’(x), where both g’(x) and h’(x) are primitives polynomials in ℤ[x], so their product is primitive, and f is primitive, too ⇒ content(abf(x)) =[f is primitive] ab = content(cdg’(x)h’(x)) =[g’(h)h’(x) is primitive] cd ⇒[ab = cd & abf(x) = cdg’(x)h’(x) & Cancellation law applies] f(x) = g’(x)h’(x) where both g’(x) and h’(x) are primitives polynomials in ℤ[x] and deg(g’(x)) = deg(g(x)) and deg(h’(x)) = deg(h(x)) and both polynomials g’ and h’ having degrees less than of f, therefore f is reducible over ℤ ∎

Mod p Irreducibility Test. Let p be a prime, f(x) ∈ ℤ[x], and deg(f(x)) ≥ 1. Let f'(x) be the polynomial in ℤp[x] obtained from f(x) by reducing all the coefficients of f(x) modulo p. If f'(x) is irreducible over ℤp and deg(f'(x)) = deg(f(x)), then f(x) is irreducible over ℚ.

Proof.

Suppose f’(x) is irreducible over ℤp and deg(f’(x)) = deg(f(x)). For the sake of contradiction, let us assume f is reducible over ℚ ⇒[Theorem. Let f(x) ∈ ℤ[x], then f(x) is irreducible over ℚ, then it is reducible over ℤ.] f is reducible over ℤ, that is, ∃g(x), h(x) ∈ ℤ[x], f(x) = g(x)h(x) with both polynomials g(x) and h(x) having degree less than of f(x) ⇒[f is reducible] 1 ≤ deg(g)< deg(f) and 1 ≤ deg(h) < deg(f). Then, the idea is that the same relationship holds taking all coefficients modulo p.

Let f’, g’, and h’ be the polynomials obtained from f, g, and h by reducing all the coefficients modulo p.

Since deg(f) = deg(f’) ⇒ deg(g’) ≤ deg(g) < deg(f’) and deg(h’) ≤ deg(h) < deg(f’) and f’ = g’h’ ⇒ f’ = g’h’, deg(g’) < deg(f’) and deg(h’) < deg(f’) ⊥ Therefore, this contradicts our assumption that f’(x) is irreducible over ℤp, so f is irreducible over ℚ.

In fact, deg(g’) = deg(g) and deg(h’) = deg(h). Otherwise, deg(f’) = deg(g’h’) = deg(g’) + deg(h’) < deg(g) + deg(h) = deg(gh) = deg(f) ⊥ By assumption, deg(f) = deg(f’).

Examples.

• f(x) = x3 + x +1 ∈ ℤ[x], x3 + x +1 ∈ ℤ/2ℤ[x], 13 +1 +1 = 3 = 1, 03+0 +1 =1, deg(f) = 3 ⇒ It is irreducible over ℤ/2ℤ ⇒ It is irreducible over ℚ.
• f(x) = x5 +9x4 +12x2 +6. f’(x) = x5 + x4 = x4(x + 1) over ℤ2, f’ is reducible over ℤ2, so we cannot apply Mod p = 2 Irreducible Test. f’(x) = x5 = x3·x2 over ℤ3, f’ is reducible over ℤ3, so we cannot apply Mod p = 3 Irreducible Test. f’(x) = x5 +4x4 + 2x2 + 1 over ℤ5. Let’s evaluate f’(0) = 1 ≠ 0, f’(1) = 3 ≠ 0, f’(2) = 10 = 0 ⇒ f’(x) = (x-2) g(x) so f’ is reducible over ℤ5, so we cannot apply Mod p = 5 Irreducible Test.
• f(x) = x3 + 7x + 16. f’(x) = x3 + 2x +1 over ℤ5. Since it has degree 3 and has no root in ℤ5[x], it is irreducible in ℤ5[x] ⇒ f(x) is irreducible in ℚ[x].
• f(x) = 21x3 -3x2 +2x +9. f’(x) = x3 +x2 +1 over ℤ2. Since it has degree 3 and has no root in ℤ2[x] (f’(0) = f’(1) = 1), it is irreducible in ℤ2[x] ⇒ f(x) is irreducible in ℚ[x]. However, f’(x) = 2x over ℤ3, f' is irreducible but 💀 we cannot apply p = 3 Irreducible Test because deg(f(x)) ≠ deg(f'(x)).
• f(x)=(3/7)x4 -(2/7)x2 + (9/35)x + 3/5. Let h(x) = 35f(x) = 15x4 -10x2 + 9x +21. h’(x) = x4 +x +1 in ℤ2[x]. It is irreducible over ℤ2[x] because it has no zeros in ℤ2[x] and has no quadratic factor either (There are two options: a) x2 + x + 1 is not a factor; b) and x2 + 1 has a zero in x=1, but h’ does not, so it is not possible h’ = (x2 + 1)·h’’) ⇒ h(x) is irreducible over ℚ ⇒ f(x) is irreducible over ℚ. (Figure 1.a.) Eisenstein Criterion. Let p ∈ ℤ be a prime. If f(x) = anxn + an-1xn-1 + ··· + a0 in ℤ[x] have degree ≥ 1 with

1. p divides all the coefficient, except the leading one, that is, p | a0, p | a1, ···, p | an-1
2. p does not divide the leading term, p ɫ an
3. p2 ɫ a0

Then, f(x) is irreducible in ℚ[x].

Proof:

This proof is by contradiction. Let’s assume that f is not irreducible. If f(x) is reducible over ℚ ⇒[Theorem. Let f(x) ∈ ℤ[x], then f(x) is irreducible over ℚ, then it is reducible over ℤ.] f is reducible over ℤ, that is, ∃g(x), h(x) ∈ ℤ[x]: f(x) = g(x)h(x) and the degrees of g and h are less than n.

Say g(x) = brxr + ··· + b0, h(x) = csxs + ··· + c0.

Since p | a0, p2 ɫ a0, and a0 = b0c0 ⇒ p divides b0 or c0, but not both. Let’s suppose p | b0 and p ɫ c0 without any loss of generality.

Since p ɫ an = brcs ⇒ p ɫ br, but p | b0, hence there is a least integer t such that p ɫ bt (p | bt-1, ··· p | b1, p| b0). Next, let us consider at = btc0 + bt-1c1 + ··· + b0ct. Then, p | at (Notice that r = deg(g(x)) = deg(brxr + ··· + b0) < n ⇒ t ≤ r < n ), and p divides every summand on the right after the first term btc0, that is, (bt-1c1 + ··· + b0ct) ⇒ p | btc0, p prime ⊥ p ɫ bt, p ɫ c0

# Examples

• f(x) = x5 +9x4 + 12x2 +6, 3 ɫ 1, 3 | 9, 3 | 12, 3 | 6, 32 = 9 ɫ 6, then f(x) is irreducible over ℚ.
• f(x) = x4 + 3x2 + 3, 3 ɫ 1, 3 | 3, 3 | 3, 32 ɫ 3, then f(x) is irreducible over ℚ.
• f(x) = 5x10 -3x7 -6x3 +15x2 -9x +6 ∈ ℤ[x], then f(x) is irreducible over ℚ (p = 3).
• xn-2 ∈ ℤ[x], n ≥ 2 is irreducible over ℚ (Eisenstein criteria, p=2) ∀n ≥ 2, so there are irreducible polynomials over ℚ of arbitrary high degree. This is not true over ℝ. We know that any irreducible polynomial over ℝ has degree 1 or 2.
• f(x) = x5 +3x3 -3x +6, 3 ɫ 1, 3 | 3, 3 | -3, 3 | 6, 32 = 9 ɫ 6, then f is irreducible over Q.
• f(x) = x2 +x +2 ∈ ℤ[x]. By changing x → x + 3, f’(x) = x2 + 6x + 9 + x + 3 + 2 = x2 + 7x + 14 is irreducible over ℚ (Eisenstein p = 7)

Eisenstein theorem applies after substitution x → x + a. If the polynomial after substitution (is is just an automorphism of the ring ℚ([x]), and automorphisms preserve algebraic properties) is irreducible then allows concluding that the original polynomial is irreducible as well.

Corollary. For any prime p, the pth cyclotomic polynomial Φp(x) = $\frac{x^p-1}{x-1}=x^{p-1}+x^{p-2}+···+x+1$ is irreducible over ℚ.

Proof. Let f(x) = Φp(x+1) = $\frac{(x+1)^p-1}{(x+1)-1}=x^{p-1}+(\begin{smallmatrix}p\\ 1\end{smallmatrix})x^{p-2}+(\begin{smallmatrix}p\\ 2\end{smallmatrix})x^{p-3}+···+(\begin{smallmatrix}p\\ p-2\end{smallmatrix})x+(\begin{smallmatrix}p\\ p-1\end{smallmatrix})1$

f(x) does satisfy the conditions of Eisenstein’s criterion because $(\begin{smallmatrix}p\\ k\end{smallmatrix})$ is divisible by p for 1 ≤ k ≤ p−1, p ɫ 1, and $(\begin{smallmatrix}p\\ p-1\end{smallmatrix})$ is not divisible by p2 ⇒ Φp(x+1) is irreducible.

But if Φp(x) = g(x)h(x) were a nontrivial factorization of Φp(x) over ℚ, then so would Φp(x+1) be no trivially factored, Φp(x+1) = g(x+1)h(x+1) ⊥

Examples: p = 2, $\frac{x^2-1}{x-1}=x+1$ is irreducible over ℚ. p = 3, $\frac{x^3-1}{x-1}=$ x2 + x + 1 is irreducible over ℚ.

Rational root test. Let f = anxn +an-1xn-1 + ··· + a0 ∈ ℤ[x], a0an ≠ 0. Each rational solution r/s written in lowest terms so that r and s are relatively prime, satisfies that r is a factor of the constant term a0 (r | a0) and s is a factor of the leading coefficient an (s | an).

Proof.

Let f = anxn +an-1xn-1 + ··· + a0 ∈ ℤ[x], let r/s be a rational solution.

anrnsn + ··· + a1rs + a0 = 0 ⇒ [Multiply by sn] anrn + an-1rn-1s + ··· + a1rsn-1 + a0sn = 0 ⇒ r(anrn-1 + ··· + a1sn-1) = -a0sn ⇒ r | a0sn ⇒ [r and s are coprime] r | a0.

Similarly, anrn + an-1rn-1s + ··· + a1rsn-1 + a0sn = 0 ⇒ s(an-1rn-1 + ··· + a1rsn-2 +a0sn-1) = -anrn ⇒ s | anrn ⇒ [r and s are coprime] s | an

# Examples

• x3-x-1, x3-3x +1 are irreducibles because any root r/s must have r = ±1, s = ±1, but they are not roots.
• 3x3-11x2+5x-3. Possible roots can be ±1, ±3, ±13. The actual rational roots of the function are 1, 3, and -13. 3x3-11x2+5x-3 = (x-1)·(x-3)·(3x+1)
• f(x) = x4 +3x2 -2x + 1 ∈ ℚ[x] is irreducible. There are two options, f(x) = linear·cubic or quadratic·quadratic.
1. f(x) = linear·cubic ⇒ there exist a zero or root associated with the linear factor, but any root r/s must have r = ±1, s = ±1, but they are not roots of f(x). f(1) = 3 ≠ 0, f(-1) = 7 ≠ 0.
2. x4 +3x2 -2x + 1 = quadratic·quadratic =[f(x) is monic] (x2 +ax +b)(x2 +cx +d) = x4 + (a + c)x3 + (b + ac + d)x2 + (ad +bc)x + bd ⇒ bd = 1, a + c = 0, b + ac + d = 3, ad + bc = -2.

bd = 1 ⇒ b = d = 1 or b = d = -1.

If b = d = 1 ⇒[ad + bc = -2] a + c = -2 ⊥ a + c = 0. Otherwise, b = d = -1 ⇒[ad + bc = -2] -a -c = -2 ⇒ a + c = 2 ⊥ a + c = 0.

# Bibliography

This content is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. This post relies heavily on the following resources, specially on NPTEL-NOC IITM, Introduction to Galois Theory, Michael Penn, and Contemporary Abstract Algebra, Joseph, A. Gallian.
1. NPTEL-NOC IITM, Introduction to Galois Theory.
2. Algebra, Second Edition, by Michael Artin.
3. LibreTexts, Abstract and Geometric Algebra, Abstract Algebra: Theory and Applications (Judson).
4. Field and Galois Theory, by Patrick Morandi. Springer.
5. Michael Penn (Abstract Algebra), and MathMajor.
6. Contemporary Abstract Algebra, Joseph, A. Gallian.
7. Andrew Misseldine: College Algebra and Abstract Algebra.
Bitcoin donation 