LCM and GCF Made Easy: Three Methods Compared
Find the least common multiple and greatest common factor by listing, by prime factors or with Euclid's algorithm. Worked examples show which method to use when.
Two questions come up again and again with whole numbers. What is the biggest number that divides into all of them? That is the greatest common factor, or GCF. What is the smallest number they all divide into? That is the least common multiple, or LCM. For 8 and 20, the GCF is 4 and the LCM is 40. Here are three ways to get there, from the simplest to the fastest.
Method 1: Write out the lists
With small numbers, listing is quick and easy to check.
- Factors of 8: 1, 2, 4, 8
- Factors of 20: 1, 2, 4, 5, 10, 20
- Largest number in both lists: 4. That is the GCF.
- Multiples of 8: 8, 16, 24, 32, 40, 48 …
- Multiples of 20: 20, 40, 60 …
- First number in both lists: 40. That is the LCM.
Listing becomes tiring once the numbers get large, so switch methods above about 50.
Method 2: Break into primes
Write each number as a product of primes. Take 45 and 75:
45 = 3² × 5 75 = 3 × 5²
- For the GCF, keep only the primes both numbers share, each at its smaller power: 3 × 5 = 15.
- For the LCM, keep every prime that appears, each at its larger power: 3² × 5² = 225.
Check: for two numbers, GCF × LCM equals the product of the numbers. 15 × 225 = 3,375, and 45 × 75 = 3,375.
Method 3: Euclid's algorithm
For big numbers, skip factoring altogether. Divide, keep the remainder, and divide again by that remainder until nothing is left. The last remainder that was not zero is the GCF. For 462 and 1071:
1071 = 2 × 462 + 147 462 = 3 × 147 + 21 147 = 7 × 21 + 0
The GCF is 21. The LCM follows from the shortcut: 462 × 1071 ÷ 21 = 23,562.
Which method should you use?
| Situation | Best method |
|---|---|
| Small numbers, under about 50 | Listing |
| Three or more numbers | Prime factors |
| Large numbers | Euclid's algorithm |
Where this shows up in real life
- Fractions: to add 3/8 + 7/20, use the LCM of 8 and 20, which is 40.
- Equal groups: 45 red and 75 blue beads can be shared into at most 15 identical bags, the GCF.
- Timing: lights that flash every 8 and every 20 seconds flash together every 40 seconds.
Tip If two numbers share no prime at all, like 9 and 16, the GCF is 1 and the LCM is simply 9 × 16 = 144.
Try it yourself: LCM & GCF CalculatorLCM and GCF of a list of numbers from their prime factorizations, checked with Euclid's algorithmOpen →Common questions
Can the GCF be bigger than the smallest number?
No. A common factor has to divide into the smallest number, so it can be at most that number.
Is the LCM always bigger than the numbers?
It is at least as big as the largest one. For 5 and 10, the LCM is 10 itself.
Do GCD and HCF mean the same as GCF?
Yes. All three names describe the same number.