# Definition:Greatest Common Divisor/Integers

## Definition

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

Then there exists a greatest element $d \in \Z_{>0}$ such that $d \divides a$ and $d \divides b$.

This is called the **greatest common divisor of $a$ and $b$** (abbreviated **GCD** or **gcd**) and denoted $\gcd \set {a, b}$.

Its existence is proved in Existence of Greatest Common Divisor.

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

Then:

- $\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$.

## Also known as

The **greatest common divisor** is also known as the **highest common factor** (abbreviated **HCF** or **hcf**) and written $\operatorname {hcf} \set {a, b}$ or $\operatorname {hcf} \tuple {a, b}$.

Alternatively, $\gcd \set {a, b}$ is written in some texts as $\tuple {a, b}$, but this notation can cause confusion with ordered pairs.

The notation $\gcd \tuple {a, b}$ is also seen, but the set notation, although a little more cumbersome, can be argued to be preferable.

The archaic term **greatest common measure** can also be found, mainly in such as Euclid's *The Elements*.

## Also see

- GCD iff Divisible by Common Divisor for an equivalent definition.

- Elements of Euclidean Domain have Greatest Common Divisor 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): $\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 - 1969: C.R.J. Clapham:
*Introduction to Abstract Algebra*... (previous) ... (next): $\S 6.28$: Example $54$ - 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$ - 1978: John S. Rose:
*A Course on Group Theory*... (previous) ... (next): $0$: Some Conventions and some Basic Facts - 1996: John F. Humphreys:
*A Course in Group Theory*... (previous) ... (next): $\text{A}.1$: Number theory: Definition $\text{A}.3$ - 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.1$: Algorithms: Algorithm $\text{E}$