---
tag: 99J1WXG3F7
kind: definition
name: Polynomial greatest common divisor
msc: [13F20, 13A05]
defines: Q75YRG25JK
uses: [0QA8CHH8MG, 0Q9EZS90GY, 0BDX4MBKT4, 0F7KNJ1ZYN]
sources:
  - url: https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor
---

## Definition

Let $K$ be a [[field|0QA8CHH8MG]] and let $f, g \in K[x]$ be polynomials that are not both $0$.
A greatest common divisor of $f$ and $g$ is a polynomial $d \in K[x]$ such that:

1. $d$ divides $f$ and $d$ divides $g$;
2. every polynomial that divides both $f$ and $g$ divides $d$.

The greatest common divisor $\gcd(f, g)$ is the unique [[monic|0BDX4MBKT4]] polynomial with these two properties.

## Remarks

Two greatest common divisors differ by a nonzero constant factor, so exactly one of them is monic.
Example: $\gcd(x^2 - 1, x^2 - 3x + 2) = x - 1$.
Check: $x - 1$ divides both, and a common divisor divides $(x^2 - 1) - (x^2 - 3x + 2) = 3x - 3$, hence divides $x - 1$.
Non-example: $2x - 2$ satisfies both clauses, but it is not monic, so it is a greatest common divisor and not $\gcd(f, g)$.
The [[Euclidean algorithm|023VY493K0]] computes $\gcd(f, g)$, and [[Bézout's identity|0VY3WPP9Y3]] gives $a, b \in K[x]$ with $a f + b g = \gcd(f, g)$.
Over a [[unique factorisation domain|06YMXJMXYS]] such as $\Z$, greatest common divisors in $\Z[x]$ also exist, but only up to units, see [[greatest common divisor in an integral domain|0F7KNJ1ZYN]].

## Explanations

### L1 human

The greatest common divisor is the largest polynomial that goes into both.
Asking for leading coefficient $1$ picks one answer among its constant multiples.