Definition:Greatest Common Divisor/Integral Domain

Definition

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.

Also known as

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

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

Also see

Note that, in the general integral domain, there is no guarantee that any GCD so defined either exists or is actually unique.

However, see Elements of Euclidean Domain have Greatest Common Divisor where it is shown that the same does not apply to a Euclidean domain.

Sources

• C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 6.28$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 62$