All about GCD and LCM
The Greatest Common Divisor (GCD) is the largest positive integer that divides two or more numbers at the same time, with no remainder.
For example, consider the numbers 12 and 18:
- Divisors of 12: 1, 2, 3, 4, 6, 12
- Divisors of 18: 1, 2, 3, 6, 9, 18
- Common divisors: 1, 2, 3, 6
The largest one is 6, therefore GCD(12, 18) = 6.
The Least Common Multiple (LCM) is the smallest non‑zero positive integer that is a multiple of two or more numbers at the same time.
Using the same numbers 12 and 18:
- Multiples of 12: 12, 24, 36, 48, 60, 72...
- Multiples of 18: 18, 36, 54, 72, 90...
- Common multiples: 36, 72...
The smallest one is 36, therefore LCM(12, 18) = 36.
The most practical way to find both GCD and LCM at the same time is simultaneous prime factorization:
- Write the numbers side by side, separated by commas.
- Divide the numbers by the smallest possible prime number (2, 3, 5, 7...) that divides at least one of them.
- If a number is not divisible, simply repeat it on the next line.
- Continue the process until all numbers become 1.
- For the LCM: multiply all prime factors used.
- For the GCD: multiply only the prime factors that divided all numbers on that line at the same time.
Practical applications
When to use the GCD?
The GCD is useful for problems of division into equal parts with the largest possible size. Example: cutting boards of different lengths into equal pieces with maximum length, or dividing candies into equal bags with no leftovers.
When to use the LCM?
The LCM solves problems of cyclic events or simultaneous occurrences. Example: determining when two buses that leave at different intervals will depart together again, or in what interval two repeating events will coincide.