Polynomial Arithmetic and GCD
Unique Factorisation Domains, Content and Primitive Parts
Content and primitive part, Gauss's lemma, and why factoring over the rationals reduces to factoring over the integers.
Engineering / MathematicsPolynomial Arithmetic and GCD2 min readKV-MATH-0558
Polynomials over a unique factorisation domain factor uniquely, but the factorisation splits into two parts: a constant content and a primitive polynomial. Separating them is the first step of every integer polynomial algorithm.
Content and primitive part
- Content
- The GCD of the coefficients, taken with a sign convention — usually positive.
- Primitive part
- The polynomial divided by its content. Its coefficients have GCD one.
- Primitive polynomial
- One whose content is one.
Gauss's lemma
The product of primitive polynomials is primitive. Equivalently, content is multiplicative.
Rational to integer reduction
A polynomial with rational coefficients is factored by clearing denominators, factoring over the integers, and reinstating the rational constant.
Factoring over the rationals
- Clear denominatorsMultiply by the least common multiple of the denominators.
- Extract contentDivide out the integer content.
- Factor the primitive partUsing integer factorisation methods.
- ReassembleReinstate the constant factor.
Content over a general UFD
The same decomposition works over any unique factorisation domain, with the coefficient GCD computed in that domain. For multivariate polynomials this is applied recursively, treating a polynomial in several variables as a polynomial in one variable over a ring of polynomials in the rest.
Why it matters for growth
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.2.2-3.2.3. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.