Calculating the GCD: two methods

Method 1: the list of divisors

We list all the divisors of each number, then identify the largest one they have in common. It’s simple but time-consuming for large numbers.

Example: GCD(20, 30)

• Divisors of 20: 1, 2, 4, 5, 10, 20
• Divisors of 30: 1, 2, 3, 5, 6, 10, 15, 30
• Common factors: 1, 2, 5, 10 -> GCD(20, 30) = 10

Method 2: Euclid’s algorithm (faster)

This method is based on the rule: GCD(a, b) = GCD(b, remainder when a is divided by b), and we stop when the remainder is 0. The GCD is then the last non-zero remainder.

Example: GCD(252, 105)

1. 252 = 105 × 2 + 42 -> we continue with (105, 42)
2. 105 = 42 × 2 + 21 -> we continue with (42, 21)
3. 42 = 21 × 2 + 0 -> the remainder is zero, so we stop

The last non-zero remainder is 21, so GCD(252, 105) = 21.

Comparison of the two methods

Method	Advantage	Disadvantage
List of divisors	Easy to understand	Time-consuming for large numbers
Euclid’s algorithm	Fast, even for large numbers	Requires divisions to be set out correctly

Common pitfalls

• Do not confuse the quotient and the remainder in Euclidean division: a = b × q + r, where 0 ≤ r < b.
• Forgetting to stop as soon as the remainder is 0: the GCD is the DIVISOR of the last line, not the previous remainder which has been misread.
• Believing that Euclid’s algorithm only works for small numbers: in fact, the opposite is true; it is particularly useful for large numbers.