# Definition:Greatest Common Divisor/Integral Domain

## Definition

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.

## 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

Note that, in the general integral domain, there is no guarantee that any GCD so defined either exists or is actually unique.

However, see Euclidean Domain is GCD Domain where it is shown that the same does not apply to a Euclidean domain.

## Sources

- 1969: C.R.J. Clapham:
*Introduction to Abstract Algebra*... (previous) ... (next): Chapter $6$: Polynomials and Euclidean Rings: $\S 28$. Highest Common Factor - 1978: Thomas A. Whitelaw:
*An Introduction to Abstract Algebra*... (previous) ... (next): $\S 62$. Factorization in an integral domain