Tutorial: Finding the greatest common divisor

One of the problems of the Malaysian education system (at least, implementation-wise) is teaching students to use algorithms without properly exploring the principle behind it, or how it "actually" works. I recall like yesterday how classmates in my pre-u classes complain about calculus being "magical". The general teaching pattern is "Just apply this series of steps mechanically, and the correct answer appears" - not a good way to foster independent thinking.

In this article we explore how to find the greatest common divisor, something that is taught in the Form One curriculum.

The greatest common divisor (GCD) of a set of numbers is the largest number that can divide all of the numbers in the set. For example, the GCD of 4 and 18 is 2, and the GCD of 6, 18, and 36 is 6. If the numbers are relatively prime, e.g. 9 and 16, the GCD will be 1.

The brute-force method to find the greatest common divisor is to list all the factors for each of the numbers, and then determine the product of all common factors that appears in the lists. For the above example, 6 decomposes to 2 and 3, 18 to 2, 3, 3, and 36 to 2, 2, 3, 3. The common factors are 2 and 3, so 2 * 3 = 6. This method is usually taught in the following form:

. 2 | 6  18  36
.     ___________
. 3 | 3   9   18
.     ___________
.      1   3    6

And the GCD is the product of the numbers on the leftmost column. Students often wonder why it is done this way. Clearly the preceding paragraph was not emphasized enough during the introduction to the topic. Drawing it in this layout is simply to make sure that the collected factors are common to all three numbers - nothing new!

Of course, this method is not efficient for large numbers, say 3456 and 2688. The following describes the Euclidean algorithm, something perhaps the ministry thinks is too advanced for 13yos.

First write it like so:
3456 = 2688 * a + b

3456/2688 will give a quotient of 1 and a remainder of 768:
3456 = 2688 * 1 + 768

Now, any divisor that divides 3456 and 2688 must also divide 768 (the remainder). To see why, imagine two numbers 10 and 4, made up of "blocks" of 2. Thus, 10 - 4 is just like 5*2 - 2*2, and the remaining 6 must also be in blocks of 2. In fact, if p divides both q and r, then q+r is still divisible by p, and so is q-r. That is because we have removed from the larger number (10, which is a multiple of 2) a certain multiple of 2 (4 = 2*2), and what remains must of course still be a multiple of 2.

This means we can reduce the problem to:
gcd(3456, 2688) = gcd(2688, 768)

Continuing,
2688 = 768 * 3 + 384
768 = 384 * 2

Therefore, gcd(3456, 2688) = 384.