The greatest common divisor, or GCD, of two or more polynomials is the highest-degree polynomial
that divides every polynomial in the list without leaving a remainder. For two polynomials
\(A(x)\) and \(B(x)\), the GCD is written as
\[
\gcd(A(x),B(x)).
\]
For example, if both polynomials contain the factor \(x+3\), then \(x+3\) is a common divisor.
The greatest common divisor is the common divisor with the largest possible degree, up to a
nonzero constant factor.
1. GCD is unique up to constants
Unlike integers, polynomial GCDs can be multiplied by any nonzero constant and still divide the
same polynomials. For instance, if \(x+1\) divides two polynomials, then \(2x+2\) also divides
them. To avoid ambiguity, most algebra tools return the monic GCD, meaning the leading
coefficient is \(1\).
\[
\text{monic GCD has leading coefficient }1.
\]
2. Polynomial division
The Euclidean algorithm depends on polynomial division. If \(A(x)\) is divided by \(B(x)\), then
there are polynomials \(Q(x)\) and \(R(x)\) such that
\[
A(x)=B(x)Q(x)+R(x),
\]
where \(R(x)=0\) or
\[
\deg R < \deg B.
\]
The polynomial \(Q(x)\) is the quotient, and \(R(x)\) is the remainder.
3. Euclidean algorithm for polynomials
The polynomial Euclidean algorithm works like the integer Euclidean algorithm. It repeatedly
replaces a pair of polynomials by the divisor and the remainder:
\[
\gcd(A,B)=\gcd(B,R).
\]
The process continues until the remainder becomes zero. The last nonzero remainder is the GCD,
usually normalized to be monic.
4. Example
Consider
\[
A(x)=x^3+5x^2+6x,
\qquad
B(x)=x^2+4x+3.
\]
Factor each polynomial:
\[
A(x)=x(x+2)(x+3),
\qquad
B(x)=(x+1)(x+3).
\]
The common factor is \(x+3\), so
\[
\gcd(A,B)=x+3.
\]
The Euclidean algorithm reaches the same result by repeated division with remainders.
5. Content and primitive part
For a polynomial with integer coefficients, the content is the greatest common divisor of
its coefficients. The primitive part is the polynomial after dividing out the content.
For example,
\[
6x^2+12x+6
\]
has coefficient content \(6\), and its primitive part is
\[
x^2+2x+1.
\]
Content and primitive parts are useful because they separate coefficient factors from polynomial
factors. This is especially helpful when comparing polynomials like \(6x^2+12x+6\) and
\(9x^2+18x+9\), where both coefficient content and variable factors matter.
6. GCD of more than two polynomials
To find the GCD of more than two polynomials, combine them pairwise:
\[
\gcd(P_1,P_2,P_3)=\gcd(\gcd(P_1,P_2),P_3).
\]
This same idea extends to any number of input polynomials. The calculator follows this pairwise
reduction process.
7. Least common multiple
The least common multiple, or LCM, of two polynomials is a polynomial that is divisible by both
inputs and has the smallest possible degree. For two nonzero polynomials,
\[
\operatorname{lcm}(A,B)=\frac{A(x)B(x)}{\gcd(A,B)}.
\]
For multiple polynomials, the LCM is also computed pairwise:
\[
\operatorname{lcm}(P_1,P_2,P_3)=\operatorname{lcm}(\operatorname{lcm}(P_1,P_2),P_3).
\]
8. Why the Euclidean algorithm is useful
Factoring polynomials can be difficult, especially for high-degree expressions. The Euclidean
algorithm avoids full factorization. Instead, it only needs division with remainder. This makes
it a powerful and reliable method for finding common polynomial factors.
9. Summary table
10. Final checklist
- Enter each polynomial in standard or factored form.
- Use polynomial division to write \(A=BQ+R\).
- Replace \(\gcd(A,B)\) by \(\gcd(B,R)\).
- Repeat until the remainder is zero.
- The last nonzero remainder is the GCD.
- Normalize the GCD, usually by making it monic.
- For more than two polynomials, apply the GCD process pairwise.
- Optionally compute the LCM using \(\operatorname{lcm}(A,B)=AB/\gcd(A,B)\).
