Euclid’s Algorithm

Euclid’s algorithm is a classic procedure beloved by computer scientists as an elegant example of recursion. While implementing the algorithm is relatively straightforward, understanding why it works it substantially trickier.

The algorithm computes the greatest common divisor (GCD) substantially faster than the naïve approach of factoring both numbers and selecting the largest factor common to both. Factorization is a notoriously slow process and Euclid’s algorithm seems magical in its efficiency.

Algorithm. For a,b such that a<b.

gcd(a,b)={bif a = 0gcd(bmoda,a)otherwise

Proposition. Euclid’s algorithm is correct.

Proof. The strategy Euclid employs here will be familiar if you know recursion. We begin with a problem and reduce it to smaller equivalent problems. We stop at some base case with a trivial solution.

The reduction step occurs in Euclid’s assertion that gcd(a,b)=gcd(bmoda,a). By the Quotient-Remainder Theorem, we know that bmoda is between 0 and a1. Therefore a is the new largest argument in our gcd function. If we repeat this reduction, eventually we will achieve an equivalent form with a 0 argument which is our base case.

We have to show gcd(0,b)=b (base case) and that gcd(a,b)=gcd(bmoda,a) (reductive step).

The base case is pretty easy. Since every integer divides 0, the gcd(0,b) is the greatest divisor of b which is simply b.

The truth of the reductive step is difficult to see intuitively. To prove gcd(a,b)=gcd(bmoda,a) it is sufficient to show that the set of all common divisors between a and b is the same as that of bmoda and a. This would mean their greatest elements (GCDs) are the same.

To show this set equality one must prove:

  1. Any common divisor of a and b divides bmoda.
  2. Any common divisor of bmoda and a divides b.

The following graphic provides some intuition.

baab mod axxxxxxxx
  1. Let x be a common divisor of a and b. Consider all of the copies of x which add up to b. Take away all the instances of x that evenly cover a. What’s left must evenly divide bmoda.
  2. Alternatively, if we consider x to be a common divisor of bmoda and a we can copy it to cover bmoda evenly and a as many times as necessary to add up to b. Therefore it evenly divides b.

If the visual demonstration is unconvincing, the above can also be shown algebraically using the definition of divisibility.

Let d be the common divisor of a and b. We can write a and b as a=dp, b=dq for p,q. By the Quotient-Remainder Theorem, we can also write b=an+(bmoda) for n,0n<a. We must show d divides bmoda.

We must also show that if d is the common divisor of bmoda and a, then it divides b. Let (bmoda)=dp, a=dq. Once again we know b=an+(bmoda).