What this calculator does
The greatest common divisor is the largest number that divides evenly into all of your numbers; the lowest common multiple is the smallest number they all divide into. One reduces, the other combines: and between them they underlie fraction arithmetic, scheduling problems and a good deal of number theory.
The Euclidean algorithm finds the GCD by repeated remainder-taking, and it has been in continuous use since around 300 BC. It remains one of the most efficient algorithms known, which is why it still sits inside modern cryptographic software.
The formula
The GCD comes from Euclid’s algorithm: replace the larger number with the remainder of dividing it by the smaller, and repeat until one becomes zero. The LCM follows from the identity that the product of two numbers equals their GCD times their LCM. For longer lists, both are applied pairwise across the list.
| Term | Meaning |
|---|---|
| GCD | Greatest common divisor, also called highest common factor. |
| LCM | Lowest common multiple. |
| Coprime | Two numbers whose only common divisor is 1. |
| Euclidean algorithm | Repeated remainder-taking to find the GCD. |
The inputs explained
| Field | What to enter |
|---|---|
| Numbers (comma separated) | Whole numbers separated by commas or spaces. Any count is accepted, and negatives are treated by their absolute value. |
When to use it
Simplifying fractions
Dividing numerator and denominator by their GCD reduces a fraction to lowest terms in one step. For 84/126 the GCD is 42, giving 2/3 immediately.
Finding a common denominator
The LCM of the denominators is the lowest common denominator. Using it rather than the product keeps the numbers manageable when adding several fractions.
Solving repeating-cycle problems
Two events recurring every 12 and 18 days coincide every 36 days: their LCM. Scheduling, gear ratios and traffic light timing all reduce to this.
Dividing into equal groups
To split 48 pens and 36 pencils into identical kits with nothing left over, the GCD of 12 gives the largest possible number of kits.
Worked examples
Every figure in the tables below is produced by this page’s own calculator at build time, so the numbers and the tool always agree. Select any row to load that scenario.
GCD and LCM of common number sets
A range of number lists, showing how the two measures behave.
| Numbers | GCD | LCM | Coprime? |
|---|---|---|---|
| 8, 12 | 4 | 24 | No: they share a factor of 4 |
| 12, 18 | 6 | 36 | No: they share a factor of 6 |
| 24, 36, 60 | 12 | 360 | No: they share a factor of 12 |
| 7, 13 | 1 | 91 | Yes |
| 15, 25, 35 | 5 | 525 | No: they share a factor of 5 |
| 100, 250, 400 | 50 | 2,000 | No: they share a factor of 50 |
How adding a number changes the result
Starting from 24 and 36 and extending the list.
| Numbers | GCD | LCM |
|---|---|---|
| 24, 36 | 12 | 72 |
| 24, 36, 60 | 12 | 360 |
| 24, 36, 60, 90 | 6 | 360 |
| 24, 36, 60, 90, 45 | 3 | 360 |
Questions
What is the difference between GCD and LCM?
The GCD is the largest number that divides all your numbers; the LCM is the smallest number all of them divide into. The GCD is never larger than the smallest input, and the LCM is never smaller than the largest.
What does coprime mean?
Two numbers are coprime when their only common divisor is 1: they share no prime factors. 8 and 15 are coprime despite neither being prime, since one factorises into twos and the other into three and five.
How does the Euclidean algorithm work?
Divide the larger by the smaller and keep the remainder. Replace the pair with the smaller number and that remainder, and repeat. When the remainder reaches zero, the last non-zero value is the GCD.
Is HCF the same as GCD?
Yes. Highest common factor and greatest common divisor are two names for the same thing, with usage varying by country and curriculum.
How do I find the GCD of more than two numbers?
Apply it pairwise: the GCD of three numbers is the GCD of the first two, then that result with the third. The same approach works for the LCM, and this calculator accepts any length of list.
For prime factorisation behind these results, see the prime factorisation calculator. For fraction arithmetic, use the fraction calculator.