In this article
Two small ideas hide behind most fraction homework and a surprising amount of real scheduling. The greatest common divisor (GCD, also called HCF) is the biggest number that divides two numbers exactly. The least common multiple (LCM) is the smallest number that both of them divide into. One tells you how to shrink, the other how to align.
Divisors you can see
A divisor of a number divides it with no remainder. The divisors of 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24 and 48. The divisors of 18 are 1, 2, 3, 6, 9 and 18. The ones that appear in both lists are the common divisors: 1, 2, 3 and 6. The largest of them, 6, is the GCD.
Listing divisors works for small numbers, but it gets slow quickly. The next two methods do not need long lists.
- Squares of side 68 across × 3 down = 24
The GCD is the side of the largest square that tiles a rectangle exactly. A 48 × 18 floor needs 24 square tiles of side 6.
Method 1: prime factors
Break each number into primes. 48 = 2⁴ × 3 and 18 = 2 × 3². For the GCD take the smaller power of each prime that both have. For the LCM take the larger power of every prime that appears.
| Prime | In 48 | In 18 | GCD uses (smaller) | LCM uses (larger) |
|---|---|---|---|---|
| 2 | 2⁴ | 2¹ | 2¹ = 2 | 2⁴ = 16 |
| 3 | 3¹ | 3² | 3¹ = 3 | 3² = 9 |
| Product | 2 × 3 = 6 | 16 × 9 = 144 |
The smaller powers give the GCD (6) and the larger powers give the LCM (144).
Method 2: Euclid’s algorithm
Written around 300 BC in Euclid’s Elements, this is one of the oldest algorithms still in everyday use. The idea: any number that divides both a and b also divides the remainder of a ÷ b. So replace the pair (a, b) by the smaller pair (b, remainder), and repeat until the remainder is zero. The last non-zero number is the GCD.
- 11071 = 2 × 462 + 147Remainder 147, so now find GCD(462, 147).
- 2462 = 3 × 147 + 21Remainder 21, so now find GCD(147, 21).
- 3147 = 7 × 21 + 0Remainder 0. The last non-zero number, 21, is the GCD.
Each step replaces the bigger number by a much smaller remainder: 1071 → 462 → 147 → 21. Three divisions are enough.
The worst cases are consecutive Fibonacci numbers, as proved by Gabriel Lamé in 1844. Even then, the step count grows with the number of digits, not the size of the numbers.
See the Fibonacci article for why those numbers are the slowest: each remainder is exactly the previous Fibonacci number, so the sequence shrinks as slowly as it can.
The GCD in action: simplifying fractions
To reduce a fraction to its simplest form, divide the top and bottom by their GCD. For 48/18 the GCD is 6, so 48 ÷ 6 = 8 and 18 ÷ 6 = 3, giving 8/3. Using the GCD guarantees the answer is fully reduced in one step; dividing by 2 and then by 3 would take two.
- 48/18 → 24/9
- 24/9 → 8/3
- Easy to stop too early
- GCD(48, 18) = 6
- 48 ÷ 6 = 8, 18 ÷ 6 = 3
- Always fully simplified
Both reach 8/3. The GCD makes sure you never stop one step short.
The LCM in action: when things line up again
Two buses leave a stop together. One returns every 12 minutes, the other every 18. They next leave together at the LCM of 12 and 18, which is 36 minutes. The same idea schedules shifts, mixed repeating tasks and gear teeth that must return to the same pairing.
- 0 minBoth leave togetherThe starting point.
- 12 minBus A againBus B is still on its way.
- 18 minBus B againBus A is waiting for its next trip.
- 24 minBus A againStill not together.
- 36 minBoth leave togetherLCM(12, 18) = 36. The pattern repeats from here.
When the two numbers share no common factor (7 and 13), the LCM is simply their product, 91. The more they share, the sooner they meet.
Quick practice
- GCD of 84 and 36? 84 = 2 × 36 + 12, 36 = 3 × 12, so 12.
- LCM of 84 and 36? 84 × 36 ÷ 12 = 252.
- Simplify 84/36. Divide both by 12 to get 7/3.
- Are 35 and 64 coprime? GCD(35, 64) = 1, so yes. Their LCM is 2,240.
Two numbers with GCD 1 are called coprime. Coprime numbers matter in encryption, where choosing keys depends on them. Read about it in prime numbers and RSA.
Questions people ask
What is the GCD of 48 and 18?
6. It is the largest number that divides both 48 and 18 exactly.
Are GCD and HCF the same thing?
Yes. HCF (highest common factor) and GCD (greatest common divisor) are different names for the same number.
How do you find the LCM from the GCD?
LCM(a, b) = a × b ÷ GCD(a, b). For 48 and 18 that is 864 ÷ 6 = 144.
What is the Euclidean algorithm?
A method that replaces (a, b) with (b, a mod b) over and over until the remainder is 0. The last non-zero value is the GCD.
What if the GCD is 1?
Then the numbers are coprime (relatively prime). Their LCM is just their product.
Where is the LCM used in everyday life?
Adding fractions with different denominators, scheduling repeating events, and gear or rotation problems all use the LCM.