Definition:Greatest Common Divisor/Integers

From ProofWiki
Jump to: navigation, search


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


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

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.