Definition:Greatest Common Divisor/Integers/Definition 2
Definition
Let $a, b \in \Z: a \ne 0 \lor b \ne 0$.
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$
where $\divides$ denotes divisibility.
This is denoted $\gcd \set {a, b}$.
When $a = b = 0$, $\gcd \set {a, b}$ is undefined.
Also defined as
Some sources gloss over the fact that at least one of $a$ and $b$ must be non-zero for $\gcd \set{ a, b }$ to be defined.
Some sources insist that both $a$ and $b$ be non-zero or strictly positive.
Some sources define $\gcd \set {a, b} = 0$ for $a = b = 0$.
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
- Results about the greatest common divisor can be found here.
Sources
- 1951: Nathan Jacobson: Lectures in Abstract Algebra: Volume $\text { I }$: Basic Concepts ... (previous) ... (next): Introduction $\S 6$: The division process in $I$
- 1969: C.R.J. Clapham: Introduction to Abstract Algebra ... (previous) ... (next): Chapter $3$: The Integers: $\S 11$. Highest Common Factor
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-2}$ Divisibility: Definition $\text {2-1}$
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Theorem $2 \text{-} 6$
- 1994: H.E. Rose: A Course in Number Theory (2nd ed.) ... (previous) ... (next): $1$ Divisibility: $1.1$ The Euclidean algorithm and unique factorization: Theorem $1.2$
- 1996: John F. Humphreys: A Course in Group Theory ... (previous) ... (next): $\text{A}.1$: Number theory: Definition $\text{A}.3$