Definition:Greatest Common Divisor

Definition

Integral Domain

Let $\left({D, +, \times}\right)$ be an integral domain whose zero is $0$.

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

Let $d \mathop \backslash a$ denote that $d$ is a divisor of $a$.

Let $d \in D$ have the following properties:

$(1): \quad d \mathop \backslash a \land d \mathop \backslash b$

$(2): \quad c \mathop \backslash a \land c \mathop \backslash b \implies c \mathop \backslash d$

Then $d$ is called a greatest common divisor of $a$ and $b$ (abbreviated GCD or gcd) and denoted $\gcd \left\{{a, b}\right\}$.

That is, in the integral domain $D$, $d$ is the GCD of $a$ and $b$ iff:

$d$ is a common divisor of $a$ and $b$

Any other common divisor of $a$ and $b$ also divides $d$.

We see that, trivially:

$\gcd \left\{{a, b}\right\} = \gcd \left\{{b, a}\right\}$

so the set notation is justified.

Integers

When the integral domain in question is the integers $\Z$, the GCD is usually defined differently, as follows:

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

Then there exists a largest $d \in \Z_{>0}$ such that $d \mathop \backslash a$ and $d \mathop \backslash b$.

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

Its existence is proved in Existence of Greatest Common Divisor.

Largest here is, of course, formally defined as maximal with respect to the ordering $\le$.

In Elements of Euclidean Domain have Greatest Common Divisor it is shown that any two GCDs of $a$ and $b$ are associates, from which it can be seen that for any two GCDs $d$ and $d\,'$ we have that $d = \pm d\,'$.

Generalization

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

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

Then:

$\gcd \left({S}\right) = \gcd \left\{{a_1, a_2, \ldots, a_n}\right\}$

is defined as the largest $d \in \Z_{>0}$ such that $\forall x \in S: d \mathop \backslash x$.

That this construction is justified is demonstrated in Greatest Common Divisor is Associative.

Equivalence of Definitions

In GCD iff Divisible by Common Divisor it is demonstrated that the definition of GCD as specified for the integers is logically equivalent to the definition as given for the GCD as specified for an integral domain.

Note, however, that an integral domain is not an ordered set and so the definition as given for integers can not apply, as there is then no concept of largest (formally: maximal).

The definition for the integral domain is an abstraction from the definition as initially encountered in grade-school arithmetic, and many treatments of number theory and abstract algebra start with the definition as given for an integral domain on which the ordering $\le$ is then applied.

When considering an ordered integral domain, it is of course possible to use either definition. It is as well to make sure which one is meant.

Variants of Notation

Alternatively, $\gcd \left\{{a, b}\right\}$ is written in some texts as $\left({a, b}\right)$, but this notation can cause confusion with ordered pairs. The notation $\gcd \left({a, b}\right)$ is also seen, but the set notation, although arguably more cumbersome, can be argued to be preferable.

It is also known as the highest common factor (abbreviated HCF or hcf) and written $\operatorname{hcf} \left\{{a, b}\right\}$ or $\operatorname{hcf} \left({a, b}\right)$.