The greatest common divisor (GCD) is the largest number that divides every value in a list exactly. The least common multiple (LCM) is the smallest number that every value divides into. Find the GCD with Euclid’s method, then get the LCM from it. The LCM and GCD calculator does both for any list of whole numbers.
Here is how each one works.
Finding the GCD with Euclid’s method
Euclid’s method finds the greatest common divisor quickly, even for large numbers. Repeatedly replace the larger number with the remainder of dividing it by the smaller, until the remainder reaches zero. The last non-zero value is the GCD.
Take 48 and 18:
| Step | Calculation | Remainder |
|---|---|---|
| 1 | 48 ÷ 18 | 12 |
| 2 | 18 ÷ 12 | 6 |
| 3 | 12 ÷ 6 | 0 |
The last non-zero remainder is 6, so the GCD of 48 and 18 is 6. The method works because any number that divides both 48 and 18 also divides their remainder, so the common divisors are preserved at every step.
Finding the LCM
Once you have the GCD, the least common multiple of two numbers follows from a simple relationship: their LCM times their GCD equals their product. Rearranged, that is LCM = a × b ÷ GCD.
For 6 and 8, the GCD is 2, so the LCM is 6 × 8 ÷ 2 = 24. Checking: 24 is a multiple of both 6 and 8, and no smaller number is, so it is correct. Dividing by the GCD first avoids the numbers getting unnecessarily large.
More than two numbers
For a longer list, work two numbers at a time. Find the GCD of the first two, then the GCD of that result with the third, and so on. The LCM extends the same way. So for 12, 18 and 24 the GCD is 6 and the LCM is 72. The LCM and GCD calculator does this across the whole list at once.
What each is used for
The two have different jobs:
- GCD reduces a fraction to lowest terms, by dividing the numerator and denominator by it.
- LCM gives the lowest common denominator when adding or comparing fractions.
- LCM also tells you when two repeating cycles line up again, like two events with different periods.
Where this comes up
These appear most in fraction work and in scheduling:
- Simplifying fractions, using the GCD of the top and bottom.
- Adding fractions, using the LCM of the denominators, covered in how to add fractions.
- Repeating events, using the LCM of their cycle lengths to find the next overlap.
Open the LCM and GCD calculator to find both for your own numbers.