# Definition:Greatest Common Divisor/Integers/Definition 1

## 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 largest $d \in \Z_{>0}$ such that $d \divides a$ and $d \divides b$

where $\divides$ denotes divisibility.

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

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

### General Definition

This definition can be extended to any (finite) number of integers.

Let $S = \set {a_1, a_2, \ldots, a_n} \subseteq \Z$ such that $\exists x \in S: x \ne 0$ (that is, at least one element of $S$ is non-zero).

### Definition 1

The **greatest common divisor** of $S$:

- $\gcd \paren S = \gcd \set {a_1, a_2, \ldots, a_n}$

is defined as the largest $d \in \Z_{>0}$ such that:

- $\forall x \in S: d \divides x$

where $\divides$ denotes divisibility.

### Definition 2

The **greatest common divisor** of $S$:

- $\gcd \paren S = \gcd \set {a_1, a_2, \ldots, a_n}$

is defined as the (strictly) positive integer $d \in \Z_{>0}$ such that:

\(\ds \forall x \in S:\) | \(\ds d \divides x \) | ||||||||

\(\ds \forall e \in \Z: \forall x \in S:\) | \(\ds e \divides x \implies e \divides d \) |

where $\divides$ denotes divisibility.

By convention:

- $\map \gcd \O = 1$

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

- 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $1$: Properties of the Natural Numbers: $\S 23$ - 1975: T.S. Blyth:
*Set Theory and Abstract Algebra*... (previous) ... (next): $\S 7$: Example $7.8$ - 1980: David M. Burton:
*Elementary Number Theory*(revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Definition $2 \text{-} 2$ - 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.1$: Algorithms: Algorithm $\text{E}$