GCD and LCM: faster alternative methods

To find the greatest common divisor (GCD) and the least common multiple (LCM), you do not always need to factor every number into primes. Euclid’s repeated divisions quickly give the GCD; the LCM follows directly from it. The same two tools work for three or more numbers. Throughout this article, we use positive integers.

What are we looking for?

The GCD is the largest positive integer that divides every given number. The LCM is the smallest positive integer that is a multiple of them all. For instance, if two events repeat every 24 and 36 minutes, the first positive time when they coincide again is the LCM. The GCD instead gives the largest unit into which both durations can be split without a remainder.

A quick GCD: repeated divisions

Let us calculate GCD(84,132). Divide the larger number by the smaller one, then replace the pair with the divisor and remainder until the remainder is zero:

132 = 84 × 1 + 48
84 = 48 × 1 + 36
48 = 36 × 1 + 12
36 = 12 × 3 + 0

The last nonzero remainder is 12, so GCD(84,132) = 12. This works because the common divisors of two numbers are exactly the common divisors of the divisor and the remainder: GCD(A,B) = GCD(B,A mod B).

Three formulas to remember

For positive integers A, B and C:

LCM(A,B) = A × B / GCD(A,B)
GCD(A,B,C) = GCD(C,GCD(A,B))
LCM(A,B,C) = LCM(C,LCM(A,B))

Work with two numbers at a time; changing their order does not change the result.

From GCD to LCM without another factorization

Using the first formula, LCM(84,132) = 84 × 132 / 12 = 84 × 11 = 924. Dividing before multiplying keeps the intermediate numbers smaller. A quick check gives 924 / 84 = 11 and 924 / 132 = 7.

Why does the formula work? In a prime factorization, the GCD takes the smaller exponent of each prime, while the LCM takes the larger one. The sum of the minimum and maximum equals the sum of the original two exponents; therefore GCD(A,B) × LCM(A,B) = A × B.

A complete example with three numbers

Take 24, 36 and 50. For the GCD, work in pairs: GCD(24,36) = 12, then GCD(50,12) = 2. Hence GCD(24,36,50) = 2.

For the LCM, first find LCM(24,36) = 24 × 36 / 12 = 72. Then GCD(72,50) = 2 and LCM(50,72) = 50 × 72 / 2 = 1800. Thus LCM(24,36,50) = 1800: indeed, 1800 / 24 = 75, 1800 / 36 = 50 and 1800 / 50 = 36.

Useful shortcuts and a mistake to avoid

• If one number is a multiple of the other, the GCD is the smaller and the LCM the larger: GCD(18,72) = 18 and LCM(18,72) = 72.
• If the GCD is 1, the numbers are coprime and their LCM is their product: LCM(35,64) = 35 × 64 = 2240.
• The two-number formula does not become A × B × C / GCD(A,B,C) for three numbers. In our example, that would give 21600 instead of 1800. Apply the formula pair by pair.

Try it yourself

Find the GCD and LCM of 18, 30 and 42 using successive pairs only.

The strategy is always the same: find the GCD quickly from remainders, then use the product divided by the GCD; for three or more numbers, repeat the process in pairs.