How to Find the GCD and LCM: Three Methods Compared

What the GCD and LCM actually are

A divisor of a number divides it with no remainder; a multiple is the number times some whole number. The greatest common divisor (GCD, also called the greatest common factor or highest common factor) of two or more integers is the largest number that divides all of them. The least common multiple (LCM) is the smallest positive number that all of them divide into.

Take 84 and 120. The divisors of 84 are 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42 and 84. The divisors of 120 are 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 and 120. They share 1, 2, 3, 4, 6 and 12, so the GCD is 12. Notice that every common divisor is itself a divisor of 12, which is always true.

When the GCD of two numbers is 1, they are called coprime or relatively prime. 8 and 15 share no prime factors, so they are coprime, and their LCM is simply their product, 120. Listing divisors works for small numbers, but it gets tedious quickly, so the methods below are what you will actually use.

Method 1: prime factorization

Breaking each number into primes makes the structure obvious. 84 = 2² × 3 × 7 and 120 = 2³ × 3 × 5.

For the GCD, take only the primes the numbers share, each raised to the smaller exponent: 2² × 3 = 12. The 5 and the 7 each appear in only one number, so they are left out. For the LCM, take every prime that appears anywhere, each raised to the larger exponent: 2³ × 3 × 5 × 7 = 840.

This method extends naturally to three or more numbers. With 12 = 2² × 3, 18 = 2 × 3² and 30 = 2 × 3 × 5, the GCD is 2 × 3 = 6 and the LCM is 2² × 3² × 5 = 180. Its weakness is that factoring large numbers by hand is slow, which is where the next methods help.

• GCD: shared primes only, smallest exponent of each
• LCM: all primes, largest exponent of each

Method 2: repeated division (the ladder method)

Many classrooms teach a ladder or cake method: write the numbers side by side, divide them by a prime that goes into all of them, write the quotients underneath, and repeat until no common prime remains.

For 84 and 120, divide by 2 to get 42 and 60, by 2 again to get 21 and 30, then by 3 to get 7 and 10. Since 7 and 10 share no factor other than 1, stop. Multiplying the primes down the left side gives the GCD, 2 × 2 × 3 = 12. Multiplying those primes by the leftover bottom row gives the LCM, 12 × 7 × 10 = 840.

It is the same arithmetic as prime factorization, just organized so you never have to factor either number completely. With three or more numbers people often keep dividing when a prime divides at least two of them, bringing the others down unchanged; in that case only the primes that divided every number count toward the GCD.

Method 3: the Euclidean algorithm

The Euclidean algorithm rests on one fact: if a divided by b leaves a remainder r, then the GCD of a and b equals the GCD of b and r. Replacing the pair with a smaller pair over and over quickly drives the remainder to zero, and you never need to factor anything.

Try 252 and 198. 252 = 198 × 1 + 54. 198 = 54 × 3 + 36. 54 = 36 × 1 + 18. 36 = 18 × 2 + 0. The last nonzero remainder, 18, is the GCD. Four divisions did the job, which is why this algorithm, more than two thousand years old, is still the one computers use.

The GCD and LCM calculator uses the Euclidean algorithm and shows the quotient and remainder at each step for the first two numbers you enter. For more than two numbers, take the GCD of the first two, then the GCD of that result with the third, and so on.

The shortcut: GCD × LCM = a × b

For any two positive integers a and b, the GCD times the LCM equals the product of the numbers. For 84 and 120, 12 × 840 = 10,080 and 84 × 120 = 10,080. In prime terms, the GCD takes the smaller exponent of each prime and the LCM takes the larger one, so together they account for every factor exactly once.

That gives a fast route to the LCM of large numbers: LCM = a × b ÷ GCD. For 252 and 198, the LCM is 252 × 198 ÷ 18 = 2,772. Finding the GCD with the Euclidean algorithm and then dividing is usually quicker than any other approach.

Be careful, though: the identity only holds for two numbers. For 12, 18 and 30, the GCD times the LCM is 6 × 180 = 1,080, while the product is 12 × 18 × 30 = 6,480. With three or more numbers, work pairwise or use prime factorization.

Fractions, schedules and tiling

Dividing the numerator and denominator by their GCD reduces a fraction to lowest terms in one step: 84/120 becomes 7/10. When adding fractions, the LCM of the denominators is the least common denominator. For 1/12 + 1/18, the LCM of 12 and 18 is 36, so the sum is 3/36 + 2/36 = 5/36.

Anything that repeats on a cycle is an LCM problem. If one bus leaves every 12 minutes and another every 18 minutes, and they depart together now, they will next depart together in 36 minutes. Splitting things into equal parts with nothing left over is a GCD problem. To cut an 84 cm by 120 cm board into identical squares with no waste, the largest possible square is 12 cm on a side, giving 7 × 10 = 70 squares.

• Events lining up again: use the LCM
• Equal groups or largest equal size: use the GCD
• 84/120 = 7/10 after dividing by the GCD of 12