1
Factorisation gives a formula
Take the minimum exponent of each prime for the gcd, and the maximum for the lcm. Correct, and it requires factoring both numbers.
Lesson · Number Theory and Cryptography · The Euclidean algorithm
Greatest Common Divisor
gcd(a,b) is the largest common divisor. Computing it from prime factorisations is correct and impractical; “The Euclidean Algorithm”'s algorithm is what makes it fast.
gcd(a,b) largest d with d | a and d | b
lcm(a,b) smallest positive m with a | m and b | m
gcd(a,b) · lcm(a,b) = |a·b|
coprime: gcd(a,b) = 1
Two quantities, one identity
Core ideas
What this lesson establishes
The definition is immediate; the interesting question is how to compute it without factoring.
2
The product identity is exact
gcd · lcm = |ab|, because min and max exponents together account for both exponents at each prime.
3
Coprime means no shared factor
gcd(a,b) = 1. Consecutive integers are always coprime, which is the fact the Chinese remainder theorem uses in “The Chinese Remainder Theorem”.
The material
gcd and lcm
The definitions, the factorisation formulas, and why they are not the method.
Definition · Greatest common divisor
For integers a, b not both zero, gcd(a,b) is the largest positive integer dividing both. gcd(a, 0) = |a|.
Definition · Least common multiple
For nonzero a, b, lcm(a,b) is the smallest positive integer divisible by both.
Theorem · From the factorisations
If a = Π p^{aᵢ} and b = Π p^{bᵢ} over the same set of primes (with zero exponents allowed), then gcd(a,b) = Π p^{min(aᵢ,bᵢ)} and lcm(a,b) = Π p^{max(aᵢ,bᵢ)}.
A common divisor may use each prime at most as often as the smaller exponent allows, and taking exactly that many gives the largest such divisor. The lcm argument is the mirror image with maxima.
□
Theorem · The product identity
gcd(a,b) · lcm(a,b) = |a · b|.
At each prime, min(aᵢ,bᵢ) + max(aᵢ,bᵢ) = aᵢ + bᵢ. Multiplying over all primes gives the identity.
□
The identity is the practical way to get an lcm: compute the gcd by Euclid's algorithm and divide. Finding the lcm directly would require the factorisations.
Example · Both, from factorisations
48 = 2⁴·3 and 180 = 2²·3²·5. gcd = 2^{min(4,2)}·3^{min(1,2)}·5^{min(0,1)} = 4·3 = 12. lcm = 2⁴·3²·5 = 720. Check: 12 · 720 = 8640 = 48 · 180.
Why factorisation is not the method
The formula requires factoring both numbers, and factoring is hard. For two 100-digit numbers no known method factors them in reasonable time, yet Euclid's algorithm computes their gcd in a few hundred divisions.
This gap is worth noticing. Computing the gcd is easy and factoring is hard, even though the formula above expresses the gcd in terms of the factorisations. An easy problem can have a hard-looking definition, and “The Euclidean Algorithm” is the reason this one is easy.
Definition · Coprime
a and b are coprime (relatively prime) when gcd(a,b) = 1: they share no prime factor. Neither number need be prime — 8 and 9 are coprime and both are composite; coprimality is a property of the pair. A set is pairwise coprime when every two of its members are.
Theorem · Consecutive integers are coprime
gcd(n, n+1) = 1 for every n.
Any common divisor d divides the difference (n+1) − n = 1, so d = 1. This is the linear-combination property of “Divisibility and the Division Algorithm”.
□
Interactive
Number theory workbench
Algorithms with their traces
Method
Computing gcd and lcm
Euclid for the gcd; the identity for the lcm.
1
Use Euclid's algorithm for the gcd
Never factorisation, unless the numbers are tiny or the factorisations are already known.
2
Get the lcm from the identity
lcm(a,b) = |ab| / gcd(a,b). Divide before multiplying to keep the numbers small.
3
Extend to several numbers by associativity
gcd(a,b,c) = gcd(gcd(a,b), c), and similarly for lcm. Note the product identity does NOT extend to three numbers.
4
Check divisibility both ways
The gcd divides both inputs; both inputs divide the lcm. Two free checks.
gcd and lcm
Score 0 / 0Choose the answer you can justify.
gcd and lcm of 84 and 264
Two routes, and a warning about the second.
BY EUCLID
264 = 3·84 + 12
84 = 7·12 + 0 ⟹ gcd = 12
lcm = 84 · 264 / 12 = 22176 / 12 = 1848
BY FACTORISATION (as a check)
84 = 2² · 3 · 7
264 = 2³ · 3 · 11
gcd = 2² · 3 = 12 ✓
lcm = 2³ · 3 · 7 · 11 = 1848 ✓
Euclid took TWO divisions. Factorisation took eight, and would
be impossible for 100-digit inputs.
For three numbers the product identity fails: gcd(2,4,8) = 2 and lcm(2,4,8) = 8, while the product is 64. The gcd and lcm still extend by associativity; only the identity relating them does not.
Common mistakes
1
Computing gcds by factoringCorrect and impractical. Euclid's algorithm is the method, and “The Euclidean Algorithm” shows why it terminates so quickly.
2
Extending the product identity to three numbersgcd(a,b,c)·lcm(a,b,c) ≠ abc in general. gcd(2,4,8) and lcm(2,4,8) multiply to 16, not 64.
3
Forgetting gcd(a,0) = |a|It is the base case of Euclid's algorithm, so getting it wrong breaks the recursion.
Check your understanding
✓
Finish when Euclid is your reflex for any gcd.
Compute gcd(1071, 462) and lcm(1071, 462) without factoring either number. The gcd takes three divisions and the lcm follows from the identity.
Note: The gap between computing gcds and factoring is one of the oldest known examples of two closely related problems with very different difficulty. RSA in “RSA Encryption” depends on that gap remaining.