Section2.3The Euclidean Algorithm

The Euclidean algorithm says that to find the gcd of \(a\) and \(b\), you do the division algorithm until you get zero as the remainder, each time replacing the old division by the new remainder, and the old number by the old division number. The last non-zero remainder is the gcd.

This procedure is named after Euclid because of this proposition in Euclid's Elements. The version linked to (an amazing complete Java interactive implementation of all the propositions, by David Joyce) has some explanation of what Euclid assumes in doing this - in particular, he basically assumes the well-ordering principle, although of course Euclid didn't think of it in these anachronistic terms.

To make the algorithm explicit: \[a=bq_1+r_1\] \[b=r_1q_2+r_2\] \[r_1=r_2q_3+r_3\] and so forth until you hit \[r_{n-2}=r_{n-1}q_{n}+0\] when you know that \(r_{n-1}\) is the greatest common divisor.

We'll prove this momentarily (2.3.1). Let's try it with the problem from last time, \(a=60\) and \(b=42\).

  • \(60=42\cdot 1+18\)
  • \(42=18\cdot 2+6\)
  • \(18=6\cdot 3+0\)
So \(gcd(60,42)=6\).

Now try it on your own by hand for the gcd of 280 and 126.

For even more practice, try this on your own with \(gcd(2013,1066)\).

Subsection2.3.1Proof of the Euclidean Algorithm

  • The division algorithm says each \(r_i\) is less than the previous one, yet they may not be less than zero. So let's apply the well-ordering principle to the set of remainders. (Think about that.) This set must have a least positive element, and that's your answer.
  • (Since \(b\) is finite, this also implies you end in a finite number of steps.)
  • Of course, that just gives a number, with no guarantee it has any connection to the gcd.
  • So consider the set of common divisors \(d\mid a\) and \(d\mid b\). Such a \(d\) also divides \(a-q_1b=1\cdot a+(-q_1)\cdot b=r_1\). So this \(d\) also divides \(b-q_2r_1=r_2\), and indeed it divides \(r_{n-3}-q_{n-1}r_{n-2}=r_{n-1}\). So all common divisors of \(a\) and \(b\) are divisors of \(r_{n-1}\).
  • And if \(d\) divides \(r_{n-1}\), it divides \(r_{n-2}=r_{n-1}q_{n}\), and thus divides \(r_{n-3}=r_{n-2}q_{n-1}+r_{n-1}\), and \(\ldots\) hence \(d\) divides \(a\) and \(b\).
  • So the sets of divisors are equal, so this algorithm really does give the gcd.

As you might expect, the proof makes more sense if you try it out with actual numbers. Especially if you can find \(a\) and \(b\) for which the algorithm takes four or five steps, you will gain some insight.