GCD and LCM Calculator
Find the greatest common divisor and least common multiple of two or more whole numbers.
About this tool
The greatest common divisor is also called the greatest common factor (GCF) or highest common factor (HCF). Enter two or more whole numbers; for two numbers the steps of Euclid’s algorithm are shown.
The greatest common divisor (GCD) is the largest number that divides into all of your numbers, and the least common multiple (LCM) is the smallest number they all divide into. You need them to simplify fractions, add fractions with different denominators, and solve scheduling problems such as when two buses next leave together. Enter two or more whole numbers to get both, with the working.
How to use the GCD and LCM Calculator
- Type two or more whole numbers, separated by commas or spaces.
- Read the GCD (also called HCF or GCF) and the LCM.
- For two numbers, follow the steps of Euclid’s algorithm underneath.
GCD and LCM of 12 and 18
The factors of 12 are 1, 2, 3, 4, 6 and 12; the factors of 18 are 1, 2, 3, 6, 9 and 18. The largest one they share is 6, so GCD(12, 18) = 6. The LCM is 12 × 18 ÷ 6 = 36, the first number in both times tables (12, 24, 36 and 18, 36). For three numbers, 4, 6 and 10, the GCD is 2 and the LCM is 60.
Euclid’s algorithm
Listing factors gets slow for big numbers, so the calculator uses Euclid’s algorithm, which is over 2,000 years old. Divide the larger number by the smaller and keep the remainder, then divide the smaller number by that remainder, and repeat until the remainder is 0. The last non-zero remainder is the GCD. For 48 and 18: 48 = 2 × 18 + 12, 18 = 1 × 12 + 6, 12 = 2 × 6 + 0, so the GCD is 6. Once you have the GCD, the LCM of two numbers is their product divided by the GCD. For more than two numbers, both are worked out two at a time. Two numbers whose GCD is 1, such as 8 and 15, are called coprime.
Frequently asked questions
Is GCD the same as HCF and GCF?
Yes. Greatest common divisor, highest common factor and greatest common factor are three names for the same thing.
How do I use the GCD to simplify a fraction?
Divide the top and bottom by their GCD. For 18/24 the GCD is 6, so it simplifies to 3/4.
When do I need the LCM?
To add fractions (the LCM of the denominators is the lowest common denominator) and for problems about repeating events, such as lights flashing every 4 and 6 seconds lining up every 12 seconds.
What is the GCD of two prime numbers?
Always 1, unless they are the same prime. Their LCM is simply their product.