How GCD and LCM are found
The Euclidean algorithm finds the GCD by repeatedly replacing the larger number with the remainder of dividing it by the smaller, until nothing is left over. The LCM then follows directly from the GCD.
- a, b — the two input numbers
- GCD — largest number that divides both a and b
- LCM — smallest number that both a and b divide into
More detail
The Euclidean algorithm, step by step
For 12 and 18: 18 mod 12 = 6, then 12 mod 6 = 0 — so the GCD is 6. Divide that out of each number (12÷6=2, 18÷6=3) and they share no more common factors. The LCM is just a×b÷GCD = 12×18÷6 = 36.
Coprime numbers
When two numbers share no common factor other than 1, they're called coprime — their GCD is 1 and their LCM is simply their product (e.g. 7 and 5 → GCD 1, LCM 35).
Where this is useful. Use GCD to reduce a fraction to lowest terms (divide numerator and denominator by it). Use LCM to find a common denominator when adding fractions, or to figure out when two repeating events line up again (e.g. buses every 12 and 18 minutes meet every 36 minutes).
Frequently asked questions
How do you find the GCD and LCM of two numbers?
The GCD comes from the Euclidean algorithm: repeatedly divide the larger number by the smaller and keep the remainder until it hits 0 — whatever's left is the GCD. The LCM is then (a × b) ÷ GCD. For 12 and 18 that's GCD 6 and LCM 36 — enter your own numbers above to see both.
How do I use LCM to add fractions with different denominators?
Find the LCM of the two denominators, convert each fraction to that common denominator, then add the numerators. E.g. 1/12 + 1/18 uses LCM(12,18) = 36 as the common denominator: 3/36 + 2/36 = 5/36.
What does it mean if two numbers are coprime?
Coprime (relatively prime) numbers share no common factor besides 1, so their GCD is exactly 1 and their LCM equals their product. 7 and 5 are coprime: GCD 1, LCM 35 — no smaller common multiple exists.
How are GCD and LCM related?
For any two positive integers, GCD(a,b) × LCM(a,b) = a × b. That identity is exactly how this calculator gets the LCM once it has found the GCD via the Euclidean algorithm.