How to Find the Greatest Common Divisor

The Method

Divide the larger number by the smaller and keep the remainder. Replace the larger number with that remainder. Repeat until the remainder is zero. The last non zero value is the GCD.

A Full Example

For 18 and 12, dividing 18 by 12 leaves a remainder of 6. Replace 18 with 6 and divide 12 by 6, which leaves a remainder of 0. The last non zero value, 6, is the GCD.

Why It Always Works

Every remainder is still a common divisor of the original pair, because anything dividing both originals divides any combination of them. Each step reduces the numbers, and the process must terminate, so the final non zero value is the largest common divisor.

How Fast It Is

For numbers of n digits the algorithm needs on the order of n steps, because the remainders shrink to roughly a quarter of the smaller number at each stage. This efficiency is what makes it the basis of the fastest known methods for very large inputs.

More Than Two Numbers

Fold the list together one at a time. The GCD of 48, 18 and 30 is found by taking the GCD of 48 and 18 first, which is 6, then the GCD of 6 and 30, which is still 6.

Verifying the Result

Divide each original number by your answer. Both must come out whole, and if you find a larger shared divisor than the one you calculated, your answer was wrong.