Definition:Greatest Common Divisor
Definition
Integral Domain
Let $\struct {D, +, \times}$ be an integral domain whose zero is $0$.
Let $a, b \in D: a \ne 0 \lor b \ne 0$.
Let $d \divides a$ denote that $d$ is a divisor of $a$.
Let $d \in D$ have the following properties:
- $(1): \quad d \divides a \land d \divides b$
- $(2): \quad c \divides a \land c \divides b \implies c \divides d$
Then $d$ is called a greatest common divisor of $a$ and $b$ (abbreviated GCD or gcd) and denoted $\gcd \set {a, b}$.
That is, in the integral domain $D$, $d$ is the GCD of $a$ and $b$ if and only if:
- $d$ is a common divisor of $a$ and $b$
- Any other common divisor of $a$ and $b$ also divides $d$.
When $a = b = 0$, $\gcd \set {a, b}$ is undefined.
We see that, trivially:
- $\gcd \set {a, b} = \gcd \set {b, a}$
so the set notation is justified.
Integers
When the integral domain in question is the integers $\Z$, the GCD is often defined differently, as follows:
The greatest common divisor of $a$ and $b$ is defined as:
- the largest $d \in \Z_{>0}$ such that $d \divides a$ and $d \divides b$
Polynomial Ring over Field
Let $F$ be a field.
Let $P, Q, R \in F \sqbrk X$ be polynomials.
Then $R$ is the greatest common divisor of $P$ and $Q$ if and only if it is a monic greatest common divisor.
This is denoted $\gcd \set {P, Q} = R$.
Real Numbers
The concept can be extended to the set of real numbers:
Let $a, b \in \R$ be commensurable.
Then there exists a greatest element $d \in \R_{>0}$ such that:
- $d \divides a$
- $d \divides b$
where $d \divides a$ denotes that $d$ is a divisor of $a$.
This is called the greatest common divisor of $a$ and $b$ and denoted $\gcd \set {a, b}$.
Also defined as
Some sources gloss over the fact that at least one of $a$ and $b$ must be non-zero for $\gcd \set{ a, b }$ to be defined.
Some sources insist that both $a$ and $b$ be non-zero or strictly positive.
Some sources define $\gcd \set {a, b} = 0$ for $a = b = 0$.
Also known as
The greatest common divisor is often seen abbreviated as GCD, gcd or g.c.d.
Some sources write $\gcd \set {a, b}$ as $\tuple {a, b}$, but this notation can cause confusion with ordered pairs.
The notation $\map \gcd {a, b}$ is frequently seen, but the set notation, although a little more cumbersome, can be argued to be preferable.
The greatest common divisor is also known as the highest common factor, or greatest common factor.
Highest common factor when it occurs, is usually abbreviated as HCF, hcf or h.c.f.
It is written $\hcf \set {a, b}$ or $\map \hcf {a, b}$.
The archaic term greatest common measure can also be found, mainly in such as Euclid's The Elements.
Also see
- Euclidean Domain is GCD Domain where it is shown that any two GCDs of $a$ and $b$ are associates.
- Results about greatest common divisors can be found here.
Sources
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): highest common factor (HCF)
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): highest common factor (HCF)