Greatest Common Divisor
The Greatest Common Divisor (GCD) of two nonzero integers a and b is the largest positive integer d that is a common divisor of both. It is denoted by $$ GCD(a, b) $$ or simply $$ (a, b) $$.
In practical terms, the GCD of two integers is the product of all the prime factors they have in common, each taken once with its lowest exponent.
Example. To find the GCD of 30 and 40, begin by factoring each number into primes: $$ 30 = 2 \cdot 3 \cdot 5 $$ $$ 40 = 2^3 \cdot 5 $$ The shared prime factors are 2 and 5, and their lowest powers are: $$ 2^1 \quad \text{and} \quad 5^1 $$ So, $$ GCD(30, 40) = 2 \cdot 5 = 10 $$
Formally, given two integers a and b in ℤ, we define an integer d as their greatest common divisor if:
- d divides both a and b: $$ d \mid a \quad \text{and} \quad d \mid b $$
- If any other integer c divides both a and b, then c also divides d: $$ \forall \ c \in \mathbb{Z}, \; c \mid a \land c \mid b \Rightarrow c \mid d $$
Note. Strictly speaking, we should say "a" greatest common divisor, since both d and −d satisfy the definition. However, by convention, "the" GCD refers to the unique positive value d, excluding its associate −d. For more on this, see associated elements.
A practical example
Let’s take a = 12 and b = 8:
$$ a = 12 \quad b = 8 $$
Their common divisors are:
$$ 1, 2, 4 $$
Therefore, $$ GCD(12, 8) = 4 $$
How to compute the GCD
One method for computing the GCD is to perform the prime factorization of each number, then identify the common factors using the smallest exponent for each.
Example
Let a = 8 and b = 48:
$$ a = 8 \quad b = 48 $$
Factoring each number:
$$ \begin{array}{c|c} a & f \\ \hline 8 & 2 \\ 4 & 2 \\ 2 & 2 \\ 1 & 1 \end{array} $$
$$ \begin{array}{c|c} b & f \\ \hline 48 & 2 \\ 24 & 2 \\ 12 & 2 \\ 6 & 2 \\ 3 & 3 \\ 1 & 1 \end{array} $$
Which gives us:
$$ a = 2^3 \quad \text{and} \quad b = 2^4 \cdot 3 $$
The only common prime factor is 2, and the lowest exponent is 3:
$$ GCD(8, 48) = 2^3 = 8 $$
Note. Prime factorization is effective for small numbers, but becomes inefficient with large values. In such cases, it’s better to use the Euclidean Algorithm, which is more practical and computationally efficient.
Properties of the GCD
The greatest common divisor satisfies the following identities:
$$ GCD(a, b) = GCD(b, a) $$
Example: $$ GCD(12, 8) = GCD(8, 12) = 4 $$
$$ GCD(a, b) = GCD(|a|, |b|) $$
Example: $$ GCD(12, 8) = GCD(-12, -8) = GCD(-12, 8) = GCD(12, -8) = 4 $$
$$ GCD(a, b) = GCD(k \cdot a, k \cdot b) $$
Example: $$ GCD(12, 8) = GCD(k \cdot 12, k \cdot 8) = 4 $$
$$ GCD(a \cdot k, b \cdot k) = |k| \cdot GCD(a, b) $$
Example: $$ GCD(12k, 8k) = |k| \cdot GCD(12, 8) = |k| \cdot 4 $$
$$ GCD(a, 0) = |a| \quad \text{for all } a \ne 0 $$
Example: $$ GCD(12, 0) = |12| = 12 $$
Division by zero is undefined in ℤ, so $$ GCD(0, 0) $$ is not defined.
Relatively Prime Numbers
Two integers a and b are said to be relatively prime (or coprime) if their GCD is 1: $$ GCD(a, b) = 1 $$
This means that a and b share no common divisors other than 1.
Example
The GCD of 4 and 5 is 1, so they are relatively prime:
$$ GCD(4, 5) = 1 $$
Note. Relatively prime numbers are not necessarily prime themselves. For example, 8 and 9 are relatively prime because they share no common divisors, yet neither is a prime number: $$ GCD(8, 9) = 1 \quad \text{but} \quad 8 = 2^3, \; 9 = 3^2 $$
The Relationship Between GCD and LCM
The greatest common divisor and the least common multiple (LCM) of two integers a and b are related by the identity: $$ LCM(a, b) = \frac{|a \cdot b|}{GCD(a, b)} $$
Example
Given a = 8 and b = 12:
$$ LCM(8, 12) = 24 $$
$$ GCD(8, 12) = 4 $$
We can confirm the relationship as follows:
$$ LCM(8, 12) = \frac{|8 \cdot 12|}{GCD(8, 12)} = \frac{96}{4} = 24 $$
The identity holds.
Bézout’s Identity
The GCD of two integers a and b can also be written as a linear combination: $$ GCD(a, b) = d = aj + bk $$ for some integers j and k.
This is known as Bézout’s identity.
And so on.
