GCD & LCM
Find the greatest common divisor and least common multiple of two or more whole numbers. Shows every step of the Euclidean algorithm and the Bézout coefficients.
What are GCD and LCM?
The greatest common divisor gcd(a, b) is the largest number that divides both a and b. You use it to simplify fractions: 252/105 = 12/5 after dividing by gcd = 21.
The least common multiple lcm(a, b) is the smallest number that both a and b divide into. You use it to add fractions with different denominators and to find when repeating cycles line up again.
Visual
Useful Identities
| Identity | Meaning |
|---|
Methods
Replace the larger number by the remainder until the remainder is 0; the last non-zero remainder is the GCD. Over 2300 years old and still the fastest method.
Factor both numbers. The GCD takes each shared prime to its lowest power; the LCM takes every prime to its highest power.
The extended Euclidean algorithm also finds integers x and y. When gcd = 1, x is the modular inverse of a mod b — essential in cryptography.
Sources & Verification
- K. H. Rosen, Elementary Number Theory and Its Applications, 6th ed., Pearson, 2011 — Ch. 3 (Primes and Greatest Common Divisors: the Euclidean algorithm).