Key takeaways
- GCD divides, LCM is divided. The GCD is a factor of both numbers; the LCM is a multiple of both.
- Prime factors make both visible. Shared primes with the lowest exponents give the GCD; all primes with the highest exponents give the LCM.
- The Euclidean algorithm is the fast route. Repeated remainders reach the GCD in a handful of steps even for large inputs.
- GCD × LCM = a × b for two positive integers, which turns one answer into the other.
- Word problems hinge on wording. “Greatest number that divides” is a GCD; “least number divisible by” is an LCM.
Two questions, one pair of numbers
For 24 and 36, the GCD is 12 and the LCM is 72. The GCD answers “what is the largest group size that splits both quantities evenly?” The LCM answers “when do two repeating schedules next line up?” Both values are built from the same prime factors, assembled in opposite directions.
Every positive integer has an infinite set of multiples and a finite set of divisors, which is why the LCM is a “least” and the GCD is a “greatest.” The GCD of 24 and 36 cannot exceed 24; the LCM cannot be smaller than 36. Those bounds catch most reversed answers before any arithmetic is checked.
Prime factorization: the definition made visible
Write each number as a product of primes. Then 24 = 2³ × 3 and 36 = 2² × 3². The GCD takes each shared prime at its lowest exponent: 2² × 3¹ = 12. The LCM takes every prime that appears, at its highest exponent: 2³ × 3² = 72.
The asymmetry is the whole method. A common factor can use at most the smaller supply of each prime, while a common multiple must contain enough of each prime to cover both numbers. For 18 = 2 × 3² and 30 = 2 × 3 × 5, the GCD is 2 × 3 = 6 and the LCM is 2 × 3² × 5 = 90.
The Euclidean algorithm
Factorization gets slow for large numbers, but the Euclidean algorithm stays fast. Divide the larger number by the smaller, replace the pair with the divisor and the remainder, and repeat until the remainder is zero; the last nonzero remainder is the GCD. For 1071 and 462:
1071 = 2 × 462 + 147
462 = 3 × 147 + 21
147 = 7 × 21 + 0
The GCD is 21. Then LCM = 1071 × 462 ÷ 21 = 494,802 ÷ 21 = 23,562. Each step shrinks the numbers at least by half in the worst case, so even 18-digit inputs finish in well under a hundred divisions.
The GCD × LCM identity
For two positive integers, GCD(a, b) × LCM(a, b) = a × b. Checking the earlier example: 12 × 72 = 864 and 24 × 36 = 864. The identity lets you compute whichever quantity is easier and divide for the other, and it explains why the LCM is never smaller than the larger input.
The identity does not extend to three numbers. For 4, 6, and 10 the GCD is 2 and the LCM is 60, but 2 × 60 = 120 while 4 × 6 × 10 = 240. Treat the shortcut as a two-number tool, and compute three-number LCMs by repeated pairing instead.
Reducing fractions
Dividing numerator and denominator by their GCD puts a fraction in lowest terms. For 42/56, the GCD is 14, so 42 ÷ 14 over 56 ÷ 14 gives 3/4. Reducing first also keeps arithmetic small: 18/24 × 32/27 becomes 3/4 × 32/27 after dividing by 6, and the product is 96/108, which reduces again to 8/9.
When a fraction is already in lowest terms, its numerator and denominator are coprime, meaning their GCD is 1. That is the definition of “simplest form,” and it is worth checking with one Euclidean step before declaring a fraction finished.
Common denominators and repeating schedules
Adding 1/6 and 1/8 requires a common denominator, and the least one is LCM(6, 8) = 24. The sum becomes 4/24 + 3/24 = 7/24. Any common multiple works, but the LCM keeps the numbers smallest and the final reduction trivial.
Schedules use the same idea. One bus leaves every 12 minutes and another every 18 minutes; they depart together every LCM(12, 18) = 36 minutes. If both leave at 7:00, the next shared departure is 7:36, then 8:12. The GCD answers a different question — the largest interval that divides both schedules evenly, which is 6 minutes.
Three or more numbers
For 24, 36, and 60, factor each: 2³ × 3, 2² × 3², and 2² × 3 × 5. The GCD is 2² × 3 = 12, the lowest power of every shared prime. The LCM is 2³ × 3² × 5 = 360, the highest power of every prime present.
With the Euclidean algorithm, combine the numbers two at a time: LCM(24, 36) = 72, then LCM(72, 60) = 360. The same reduction works for the GCD, and the order does not change the result. A calculator that accepts only two inputs can still handle a list this way.
Word problems: greatest divisor versus least multiple
“Find the greatest number that divides 43 and 91, leaving a remainder of 7.” Subtract the remainder first: 43 − 7 = 36 and 91 − 7 = 84. The answer must divide both, so it is GCD(36, 84) = 12. Check: 43 ÷ 12 = 3 remainder 7, and 91 ÷ 12 = 7 remainder 7.
“Find the least number that leaves a remainder of 5 when divided by 6, 8, and 12.” Here the number is 5 more than a common multiple, so LCM(6, 8, 12) = 24 and the answer is 29. The trivial answer 5 also leaves that remainder, which is why well-posed problems ask for a number greater than the divisors.
Tiling is a GCD problem in disguise: a 48-inch by 36-inch surface covered by the largest square tiles needs tiles of GCD(48, 36) = 12 inches, and the count is (48 ÷ 12) × (36 ÷ 12) = 4 × 3 = 12 tiles. Grab-bag problems — equal piles from 24 pencils and 36 erasers — ask for the GCD, because the pile size must divide both counts.
Common mistakes
- Swapping the two answers: using the LCM where a largest common factor is needed, or the GCD for a shared schedule.
- Taking the lowest exponent for the LCM or the highest for the GCD, which produces a multiple that is too small or a divisor that does not divide.
- Using the GCD × LCM identity on three or more numbers.
- Forgetting to subtract the remainder before applying the GCD in a remainder problem.
- Reporting the LCM as the product of the inputs when the numbers share a factor; 24 × 36 = 864, not 72.
- Assuming LCM(a, b) is always a × b; that only holds when a and b are coprime.
Practical caveats
Both quantities are defined for positive integers; most calculators reject zero or take GCD(a, 0) = a as a convention. Negative inputs are usually converted to absolute values, since divisibility ignores sign. The LCM identity also breaks down for non-integers, so convert decimals to fractions before using it.
The LCM can grow quickly — for 97, 89, and 83, three primes, it is the product, 716,539 — but the GCD of large numbers stays small and cheap to compute. In code, use the Euclidean algorithm with the modulo operator and watch for the case where one input is zero.
Frequently asked questions
Is the GCD always smaller than the LCM?
Yes, for positive integers greater than 1. The GCD divides both numbers and the LCM is a multiple of both, so the GCD is at most the smaller input and the LCM is at least the larger one.
What does “coprime” mean?
Two numbers are coprime when their only common factor is 1, so GCD = 1. For example, 8 and 15 are coprime, and their LCM is their product, 120.
Can the GCD be 1?
Yes. Consecutive integers always have a GCD of 1, as do any two numbers with no shared prime factor. A GCD of 1 does not mean the numbers are prime.
How do I find the LCM of three numbers?
Pair them up: LCM(a, b) first, then LCM of that result with c. Alternatively, factor all three and take the highest power of every prime that appears.
Why does GCD × LCM equal a × b?
Each prime’s exponent in the GCD is the minimum of its two exponents, and in the LCM the maximum. Minimum plus maximum equals the sum of the two exponents, which is exactly what the product a × b contains.
What is the LCM of two numbers that share no factors?
Their product. If GCD = 1, the identity gives LCM = a × b ÷ 1. For 9 and 14, the LCM is 126.
Further reading