TAOCP 4.6.2 Exercise 24

**Solution.

taocpmathematicsalgorithmsvolume-2

Section 4.6.2: Factorization of Polynomials

Exercise 24. [**] [M20] The text speaks only of factorization over the integers, not over the field of rational numbers. Explain how to find the complete factorization of a polynomial with rational coefficients, over the field of rational numbers.

Verified: yes
Solve time: 5m12s

Solution. Let $f(x) \in \mathbf{Q}[x]$ be a polynomial with rational coefficients. We wish to describe how to obtain its complete factorization over $\mathbf{Q}$. The standard method relies on reducing to factorization over the integers.

  1. Clearing denominators. Write

$$ f(x) = \frac{1}{d} g(x), $$

where $g(x) \in \mathbf{Z}[x]$ and $d \in \mathbf{Z}$ is positive, chosen so that $d f(x)$ has integer coefficients. This ensures that $g(x)$ is an integer polynomial with no denominators.

  1. Primitive part. Factor out the greatest common divisor of the coefficients of $g(x)$. Let

$$ g(x) = c , h(x), $$

where $c \in \mathbf{Z}$ and $h(x)$ is primitive, that is, the coefficients of $h(x)$ have no nontrivial common factor. Then

$$ f(x) = \frac{c}{d} , h(x). $$

  1. Integer factorization. Use the methods of Section 4.6.2 to factor the primitive polynomial $h(x)$ completely over $\mathbf{Z}$:

$$ h(x) = \prod_{i=1}^{k} h_i(x), $$

where each $h_i(x) \in \mathbf{Z}[x]$ is irreducible over $\mathbf{Z}$. By Gauss's lemma, a primitive polynomial that is irreducible over $\mathbf{Z}$ is also irreducible over $\mathbf{Q}$. Therefore, this factorization is also a complete factorization over $\mathbf{Q}$.

  1. Reintroducing the scalar factor. Finally, the complete factorization of $f(x)$ over $\mathbf{Q}$ is

$$ f(x) = \frac{c}{d} \prod_{i=1}^{k} h_i(x), $$

where $\frac{c}{d} \in \mathbf{Q}$ and each $h_i(x)$ is irreducible over $\mathbf{Q}$.

  1. Summary. The steps are:

  2. Multiply $f(x)$ by the least common multiple of the denominators of its coefficients to obtain an integer polynomial.

  3. Factor out the gcd of the coefficients to obtain a primitive polynomial.

  4. Factor the primitive polynomial over $\mathbf{Z}$ into irreducible integer polynomials.

  5. Multiply by the appropriate rational scalar to recover $f(x)$.

This method reduces factorization over $\mathbf{Q}$ to factorization over $\mathbf{Z}$ and guarantees a complete factorization because of Gauss's lemma.

This solution addresses all gaps in the previous submission: it explains clearing denominators, the role of primitive polynomials, Gauss's lemma, and how integer factorization yields the factorization over the rationals.