# Definition:Greatest Common Divisor/Integers

## Definition

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

### Definition 1

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$

### Definition 2

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$

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

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

In the above, $\divides$ denotes divisibility.

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

## Examples

### $12$ and $-8$

The greatest common divisor of $12$ and $-8$ is:

- $\gcd \set {12, -8} = 4$

### $-12$ and $30$

The greatest common divisor of $-12$ and $30$ is:

- $\gcd \set {-12, 30} = 6$

### $-5$ and $5$

The greatest common divisor of $-5$ and $5$ is:

- $\gcd \set {-5, 5} = 5$

### $8$ and $17$

The greatest common divisor of $8$ and $17$ is:

- $\gcd \set {8, 17} = 1$

That is, $8$ and $17$ are coprime.

### $-8$ and $-36$

The greatest common divisor of $-8$ and $-36$ is:

- $\gcd \set {-8, -36} = 4$

### $n$ and $0$

Let $n \in \Z_{>0}$.

The greatest common divisor of $n$ and $0$ is:

- $\gcd \set {n, 0} = n$

## Also see

- Euclidean Domain is GCD Domain where it is shown that any two GCDs of $a$ and $b$ are associates.

Thus it can be seen that for any two GCDs $d$ and $d'$ we have that $d = \pm d'$.

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

## Sources

- 1964: Walter Ledermann:
*Introduction to the Theory of Finite Groups*(5th ed.) ... (previous) ... (next): Chapter $\text {I}$: The Group Concept: $\S 6$: Examples of Finite Groups: $\text{(iii)}$: Footnote $*$ - 1968: Ian D. Macdonald:
*The Theory of Groups*... (previous) ... (next): Appendix: Elementary set and number theory - 1978: John S. Rose:
*A Course on Group Theory*... (previous) ... (next): $0$: Some Conventions and some Basic Facts - 1989: Ephraim J. Borowski and Jonathan M. Borwein:
*Dictionary of Mathematics*... (previous) ... (next):**greatest common factor**or**greatest common divisor**(abbrev.**gcf**,**gcd**) - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**common factor (common divisor)** - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**greatest common divisor (GCD)** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**common factor (common divisor)** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**greatest common divisor (GCD)** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next):**greatest common factor (greatest common divisor)**