Definition:Greatest Common Divisor/Integers
Definition
Let $a, b \in \Z: a \ne 0 \lor b \ne 0$.
Definition 1
The greatest common divisor of $a$ and $b$ is defined as:
- the largest $d \in \Z_{>0}$ such that $d \divides a$ and $d \divides b$
Definition 2
The greatest common divisor of $a$ and $b$ is defined as the (strictly) positive integer $d \in \Z_{>0}$ such that:
- $(1): \quad d \divides a \land d \divides b$
- $(2): \quad c \divides a \land c \divides b \implies c \divides d$
This is denoted $\gcd \set {a, b}$.
When $a = b = 0$, $\gcd \set {a, b}$ is undefined.
In the above, $\divides$ denotes divisibility.
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).
Definition 1
The greatest common divisor of $S$:
- $\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$
where $\divides$ denotes divisibility.
Definition 2
The greatest common divisor of $S$:
- $\gcd \paren S = \gcd \set {a_1, a_2, \ldots, a_n}$
is defined as the (strictly) positive integer $d \in \Z_{>0}$ such that:
\(\ds \forall x \in S:\) | \(\ds d \divides x \) | ||||||||
\(\ds \forall e \in \Z: \forall x \in S:\) | \(\ds e \divides x \implies e \divides d \) |
where $\divides$ denotes divisibility.
By convention:
- $\map \gcd \O = 1$
Also known as
The greatest common divisor is often seen abbreviated as GCD, gcd or g.c.d.
Some sources write $\gcd \set {a, b}$ as $\tuple {a, b}$, but this notation can cause confusion with ordered pairs.
The notation $\map \gcd {a, b}$ is frequently seen, but the set notation, although a little more cumbersome, can be argued to be preferable.
The greatest common divisor is also known as the highest common factor, or greatest common factor.
Highest common factor when it occurs, is usually abbreviated as HCF, hcf or h.c.f.
It is written $\hcf \set {a, b}$ or $\map \hcf {a, b}$.
The archaic term greatest common measure can also be found, mainly in such as Euclid's The Elements.
Examples
$12$ and $-8$
The greatest common divisor of $12$ and $-8$ is:
- $\gcd \set {12, -8} = 4$
$-12$ and $30$
The greatest common divisor of $-12$ and $30$ is:
- $\gcd \set {-12, 30} = 6$
$-5$ and $5$
The greatest common divisor of $-5$ and $5$ is:
- $\gcd \set {-5, 5} = 5$
$8$ and $17$
The greatest common divisor of $8$ and $17$ is:
- $\gcd \set {8, 17} = 1$
That is, $8$ and $17$ are coprime.
$-8$ and $-36$
The greatest common divisor of $-8$ and $-36$ is:
- $\gcd \set {-8, -36} = 4$
$n$ and $0$
Let $n \in \Z_{>0}$.
The greatest common divisor of $n$ and $0$ is:
- $\gcd \set {n, 0} = n$
Also see
- Euclidean Domain is GCD Domain 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): Chapter $\text {I}$: The Group Concept: $\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
- 1978: John S. Rose: A Course on Group Theory ... (previous) ... (next): $0$: Some Conventions and some Basic Facts
- 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): greatest common factor or greatest common divisor (abbrev. gcf, gcd)
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): common factor (common divisor)
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): greatest common divisor (GCD)
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): common factor (common divisor)
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): greatest common divisor (GCD)
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): greatest common factor (greatest common divisor)