What each one means
The greatest common divisor is the largest number that divides all the inputs without remainder. For 48 and 180 it is 12, because 12 divides both and nothing larger does.
The lowest common multiple is the smallest number that all the inputs divide into. For 4 and 6 it is 12.
They are linked by an identity that makes computing the LCM straightforward:
GCD(a, b) × LCM(a, b) = a × b
So LCM(a, b) = (a × b) ÷ GCD(a, b). Dividing before multiplying avoids overflow on large inputs.
The Euclidean algorithm
Finding the GCD by listing all divisors is slow. The Euclidean algorithm, described around 300 BC and still the standard method, is remarkably efficient.
The rule is: replace the larger number with the remainder of dividing it by the smaller, and repeat until the remainder is zero. The last non-zero value is the GCD.
For 48 and 180: 180 mod 48 = 36, then 48 mod 36 = 12, then 36 mod 12 = 0. The GCD is 12 — three steps.
The algorithm runs in logarithmic time, so even numbers with hundreds of digits resolve almost instantly. Its worst case occurs with consecutive Fibonacci numbers, which is a pleasing piece of mathematical trivia and also the basis of its complexity proof.
Where GCD is actually used
Simplifying fractions. Divide numerator and denominator by their GCD. 48/180 reduces to 4/15 in one step.
Aspect ratios. 1920:1080 reduces to 16:9 by dividing both by their GCD of 120.
Cryptography. RSA key generation requires finding numbers that are coprime — GCD of 1 — and the extended Euclidean algorithm computes the modular inverse that forms the private key.
Modular arithmetic. A modular inverse exists only when the values are coprime, which is checked with the GCD.
Scheduling and gear ratios. Any problem involving cycles that must align uses one or both of these.
Where LCM is used
Adding fractions. The lowest common denominator is the LCM of the denominators. For 1/4 + 1/6, the LCM of 4 and 6 is 12, giving 3/12 + 2/12 = 5/12.
Recurring events. If one process repeats every 12 days and another every 18, they coincide every LCM(12,18) = 36 days. This is the standard approach for cron-like scheduling questions.
Cyclic systems. Gear teeth, traffic light cycles, and polling intervals all use LCM to determine when states repeat.
A practical caution: LCM grows very quickly with several inputs. The LCM of the numbers 1 through 20 is already over 232 million.
Coprime numbers
Two numbers are coprime (or relatively prime) when their GCD is 1 — they share no common factor other than 1. Note this does not require either to be prime: 8 and 15 are coprime despite both being composite.
Coprimality matters in several places. In cryptography, RSA requires the public exponent to be coprime with a particular value. In hashing, a table size coprime with the step size guarantees a probing sequence visits every slot. And in fraction arithmetic, a fraction is in lowest terms precisely when numerator and denominator are coprime.
A curious result: the probability that two randomly chosen integers are coprime is 6/π², or about 61%.
Frequently asked questions
What is the Euclidean algorithm?
A method for finding the GCD by repeatedly replacing the larger number with the remainder of dividing it by the smaller, until the remainder is zero. It dates to around 300 BC and runs in logarithmic time.
How are GCD and LCM related?
GCD(a,b) multiplied by LCM(a,b) equals a times b. So the LCM can be found as (a times b) divided by the GCD, which is far faster than searching for multiples.
What does coprime mean?
Two numbers are coprime when their GCD is 1, sharing no factor other than 1. Neither needs to be prime - 8 and 15 are coprime despite both being composite.
Where is GCD used in real applications?
Simplifying fractions and aspect ratios, RSA key generation, modular inverses in cryptography, and any problem involving aligning repeating cycles.