GCD and LCM: How to Find the Greatest Common Divisor and Least Common Multiple
The GCD, greatest common divisor (also called HCF, highest common factor), is the largest number that divides two or more integers with nothing left over. The LCM, least common multiple, is the smallest positive number that all of them divide into evenly. Take 12 and 18: the GCD is 6, the LCM is 36. Both numbers show up together constantly, and knowing how to get from a and b to each one by hand is a genuinely useful skill, not just a homework exercise.
These two numbers turn up anywhere quantities need to line up. Adding fractions with different denominators means finding an LCM (the lowest common denominator). Simplifying a fraction or a ratio means dividing by a GCD. Two gears with different tooth counts return to the same alignment after a number of rotations tied to their LCM. Anything that repeats on a cycle, a bus schedule, a blinking light, a recurring task, syncs back up with another cycle at their LCM. Scaling a recipe or a mix down to the smallest whole-number proportions means dividing every quantity by their shared GCD.
The Euclidean algorithm
The fastest way to find the GCD of two numbers by hand doesn’t involve listing factors at all. For a > b:
- Divide a by b and note the remainder, r.
- Replace a with b, and replace b with r.
- Repeat until r is 0. The last non-zero value of b is the GCD.
Once you have the GCD, the LCM follows from a single division: LCM(a, b) = (a × b) / GCD(a, b).
Here’s the algorithm running on 12 and 18:
| Dividend | Divisor | Quotient | Remainder |
|---|---|---|---|
| 18 | 12 | 1 | 6 |
| 12 | 6 | 2 | 0 |
The remainder hit 0 on the second line, so the GCD is the divisor from that step: 6. Plugging that into the LCM formula gives (12 × 18) / 6 = 216 / 6 = 36.
That LCM of 36 is exactly the lowest common denominator you’d need to add 1/12 + 1/18. Converting both fractions over 36 gives 1/12 = 3/36 and 1/18 = 2/36, so the sum is 5/36. The GCD of 6 plays a different role: it’s what you’d divide by to simplify 12/18 down to 2/3, its lowest terms. Same two numbers, two separate jobs.
Why GCD × LCM = a × b only works for two numbers
For any two numbers, there’s a neat identity: GCD(a, b) × LCM(a, b) = a × b. Check it against 12 and 18: 6 × 36 = 216, and 12 × 18 = 216. They match, and that’s not a coincidence, it holds for every pair of integers.
It’s tempting to assume the same identity scales up once you add a third number, and that’s a genuine mistake worth flagging: it doesn’t. GCD(a, b, c) × LCM(a, b, c) is not generally equal to a × b × c once you’re past two numbers. The relationship between GCD and LCM for three or more values is more involved than a single multiplication, so don’t reach for this shortcut outside the two-number case.
Working with three numbers
Scheduling: LCM of three numbers
Say one task repeats every 4 days, a second every 6 days, and a third every 15 days. When do all three coincide again? That’s the LCM of 4, 6 and 15, and you can get there by combining pairs one at a time: first LCM(4, 6) = 12, then LCM(12, 15). For that second step, GCD(12, 15) = 3, so LCM(12, 15) = (12 × 15) / 3 = 60. All three tasks land on the same day again after 60 days.
Simplifying a ratio: GCD of three numbers
The same pairwise approach works for GCD. Take 36, 60 and 84, numbers you might be trying to reduce to the smallest whole-number ratio. GCD(36, 60) = 12, and then GCD(12, 84) = 12 as well, so GCD(36, 60, 84) = 12. Divide all three by 12 and you get 3, 5 and 7, the simplest form of that ratio. This is exactly the move you’d make scaling a recipe or a batch mix down to the smallest whole quantities that keep the same proportions.
Prime factorization: an alternative method
The Euclidean algorithm is the quickest route for two numbers, but prime factorization is often clearer once there are three or more values involved, or when you want to see exactly why the answer comes out the way it does.
Break 12 and 18 into their prime factors: 12 = 2² × 3, and 18 = 2 × 3².
For the GCD, take the lowest power of every prime the two numbers share: 2¹ × 3¹ = 6. For the LCM, take the highest power of every prime that shows up in either number: 2² × 3² = 4 × 9 = 36.
Both answers, GCD 6 and LCM 36, match what the Euclidean algorithm gave earlier. That agreement is a good habit to check for whenever you’re doing this by hand: if the two methods disagree, one of them has an arithmetic slip somewhere.
A real-world example: gear ratios
Picture two meshing gears, one with 48 teeth and one with 18. The GCD of 48 and 18 is 6, so the tooth ratio reduces to 48/6 : 18/6, which is 8:3. That’s the simplest whole-number description of how the two gears relate to each other.
The LCM answers a different question: how many rotations pass before both gears are back at their exact starting alignment at the same moment? LCM(48, 18) = 144. The 48-tooth gear completes 144/48 = 3 full rotations in that time, and the 18-tooth gear completes 144/18 = 8 full rotations. Three turns of the big gear and eight turns of the small one land both gears back where they started, together.
Calculate with your own numbers
Separate values with commas, spaces or new lines. Decimals are ignored.
Enter at least two integers to see the GCD and LCM.
- Numbers
- —
- Coprime
- —
Prime factorization
Euclidean algorithm
Common mistakes and edge cases
- Mixing up GCD and LCM. The GCD is always the smaller of the two values (or equal), the LCM is always the larger (or equal). If your GCD comes out bigger than your LCM, something went wrong.
- Applying GCD × LCM = a × b to three or more numbers. As covered above, that identity is a two-number rule only.
- Forgetting the zero convention. LCM(anything, 0) is conventionally 0, since nothing is a common multiple of 0 and a positive integer. GCD(0, n), on the other hand, is just n.
- Using the LCD when you meant the GCD, or vice versa. Finding a common denominator to add fractions calls for an LCM. Reducing a fraction to lowest terms calls for a GCD. They’re easy to swap by habit, especially under time pressure.
FAQ
Does GCD × LCM = a × b work for three or more numbers? No. That identity is only guaranteed for exactly two numbers. For 12 and 18 it holds (6 × 36 = 216 = 12 × 18), but for three numbers like 36, 60 and 84, multiplying the GCD by the LCM does not generally equal the product of all three values. Combine the numbers pairwise instead, as shown in the three-number examples above.
What is the fastest way to find the GCD of two large numbers by hand? The Euclidean algorithm. Listing every factor of a large number gets slow fast, but repeated division (divide, keep the remainder, repeat) reaches the GCD in only a handful of steps, even for numbers in the thousands or millions.
Can GCD or LCM be zero or negative? GCD and LCM are defined for positive integers. By convention, GCD(0, n) equals n, and LCM(anything, 0) equals 0. A calculator will typically take the absolute value of any negative input before computing either result.
How is this different from just listing common factors or multiples? Listing factors of each number and picking the largest one they share works fine for small values, and listing multiples until one matches works for LCM the same way. Both approaches get impractical once the numbers grow, though. The Euclidean algorithm and prime factorization reach the same answer in far fewer steps and scale to numbers you’d never want to factor by hand.