What is a GCD & LCM Calculator?
This calculator finds the greatest common divisor (GCD) and least common multiple (LCM) of numbers — used for simplifying fractions and finding when repeating cycles align.
How it's calculated
The Euclidean algorithm finds GCD, and then GCD × LCM = the product of the two numbers gives the LCM.
Step-by-step example
Finding the GCD of 48 and 18
- Step 1 48÷18 = 2 remainder 12
- Step 2 18÷12 = 1 remainder 6
- Step 3 12÷6 = 2 remainder 0 → GCD = 6
Interpretation: The LCM follows directly as (48×18)÷6 = 144, once you know the GCD.
A 2,300-year-old algorithm
The Euclidean algorithm, described in Euclid's Elements around 300 BCE, is still exactly the algorithm computers use today. It works by repeatedly replacing the larger number with the remainder of dividing it by the smaller, until the remainder is 0.
48 and 18 → remainder 12 → remainder 6 → remainder 0 → answer: 6
Good to know
- Since GCD × LCM = the product of two numbers, once you know one you can find the other with a single division.
- Gears returning to their starting alignment, or two buses on different schedules arriving together — these are all LCM problems.
- The famous 13-year and 17-year cicada cycles are widely explained by the 'prime number hypothesis': a prime-numbered cycle minimizes the LCM overlap with predator cycles, reducing the chance of encountering them.
- When two numbers' GCD is 1, they're called coprime — a foundational concept in cryptography.
- The Euclidean algorithm's core idea — repeated mutual division — is essentially self-descriptive in its name.
Frequently asked questions
Q. What is GCD used for?
Simplifying fractions, dividing items evenly with nothing left over, and tiling a rectangle with the largest possible squares.
Q. What is LCM used for?
Finding a common denominator for fractions, and calculating when different-length cycles (bus schedules, gears, signal timing) realign.
Q. Can this work for three or more numbers?
Yes. Compute pairwise: GCD(a,b,c) = GCD(GCD(a,b), c).