# Definition:Greatest Common Divisor/Integers/Definition 2

## Definition

Let $a, b \in \Z: a \ne 0 \lor b \ne 0$.

The **greatest common divisor of $a$ and $b$** is defined as the (strictly) positive integer $d \in \Z_{>0}$ such that:

- $(1): \quad d \divides a \land d \divides b$
- $(2): \quad c \divides a \land c \divides b \implies c \divides d$

where $\divides$ denotes divisibility.

This is denoted $\gcd \set {a, b}$.

When $a = b = 0$, $\gcd \set {a, b}$ is undefined.

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

- Results about
**the greatest common divisor**can be found**here**.

## Sources

- 1951: Nathan Jacobson:
*Lectures in Abstract Algebra: Volume $\text { I }$: Basic Concepts*... (previous) ... (next): Introduction $\S 6$: The division process in $I$ - 1969: C.R.J. Clapham:
*Introduction to Abstract Algebra*... (previous) ... (next): Chapter $3$: The Integers: $\S 11$. Highest Common Factor - 1971: George E. Andrews:
*Number Theory*... (previous) ... (next): $\text {2-2}$ Divisibility: Definition $\text {2-1}$ - 1980: David M. Burton:
*Elementary Number Theory*(revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Theorem $2 \text{-} 6$ - 1994: H.E. Rose:
*A Course in Number Theory*(2nd ed.) ... (previous) ... (next): $1$ Divisibility: $1.1$ The Euclidean algorithm and unique factorization: Theorem $1.2$ - 1996: John F. Humphreys:
*A Course in Group Theory*... (previous) ... (next): $\text{A}.1$: Number theory: Definition $\text{A}.3$