Definition:Greatest Common Divisor/Integers
Contents |
Definition
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.
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)$.
Sources
- C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 3.11$
- C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 6.28$: Example $54$
- George E. Andrews: Number Theory (1971): $\S 2.2$: Definition $2.1$
- Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 23$
- Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 12$
- John F. Humphreys: A Course in Group Theory (1996): $\text{A}.1$: Definition $\text{A}.3$
