# Definition:Greatest Common Divisor/Integers/General Definition

## Contents

## Definition

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

- Greatest Common Divisor is Associative for a justification of this construction.

## Sources

- 1971: George E. Andrews:
*Number Theory*... (previous) ... (next): $\S 2.4$: Exercise $10$ - 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $1$: Properties of the Natural Numbers: $\S 23 \theta$ - 1978: Thomas A. Whitelaw:
*An Introduction to Abstract Algebra*... (previous) ... (next): $\S 12$: Highest common factors and Euclid's algorithm