Polynomial Arithmetic and GCD
Polynomial Division with Remainder
Euclidean division of polynomials, pseudo-division over a ring without inverses, and the coefficient growth pseudo-division introduces.
Engineering / MathematicsPolynomial Arithmetic and GCD2 min readKV-MATH-0556
Polynomial division with remainder requires the leading coefficient of the divisor to be invertible. Over a field that is automatic; over the integers it is not, and the workaround is the source of a great deal of coefficient growth.
Division over a field
Euclidean division of polynomials
- Compare degreesIf the dividend has lower degree, the quotient is zero and the remainder is the dividend.
- Form the termDivide the leading coefficient of the dividend by that of the divisor; the degree difference gives the exponent.
- SubtractSubtract that term times the divisor from the dividend.
- RepeatContinue until the degree drops below that of the divisor.
Pseudo-division
Over a ring without inverses, multiply the dividend by a power of the divisor's leading coefficient first, making every division in the process exact.
Exact division
When a polynomial is known in advance to divide another exactly, the remainder computation can be skipped and the quotient built directly. This is common — dividing out a known factor after squarefree factorisation, for instance.
Fast division
As with integers, division reduces to multiplication by computing an approximate reciprocal via Newton iteration on the reversed polynomial. The cost becomes O(M(d)), worthwhile only at high degree.
Growth control
| Approach | Effect |
|---|---|
| Pseudo-division | Exact but coefficients grow badly |
| Divide by content at each step | Primitive remainder sequence; slow but bounded |
| Sub-resultant | Predicts the removable factor; the standard answer |
| Modular methods | Work modulo primes and reconstruct; avoids the problem entirely |
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.1.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.