Definition:Greatest Common Divisor of Set of Integers/Definition 1
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).
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.
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.
Also see
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-4}$ The Fundamental Theorem of Arithmetic: 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