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.
We'll state and prove this momentarily (Algorithm 2.3.2). Let's try it with a reasonably sized problem, \(a=60\) and \(b=42\).
\begin{align*}
60&=42\cdot 1+18\\
42&=18\cdot 2+6\\
18&=6\cdot 3+0
\end{align*}
So \(\gcd(60,42)=6\).
This procedure is named after Euclid because of this proposition in Euclid's Elements. There is an amazing complete Java interactive implementation of all the propositions, by David Joyce; his version of this proposition includes some explanation of what Euclid assumes in doing this. In particular, Euclid basically assumes the Well-Ordering Principle, although of course he didn't think of it in such anachronistic terms.
Try the algorithm on your own by hand for the gcd of 280 and 126. Or, for even more practice, try it with \(\gcd(2013,1066)\) and then check your work with Sage.
Algorithm2.3.2Euclidean algorithm
To get the greatest common divisor of \(a\) and \(b\), perform the division algorithm until you hit a remainder of zero, as below.
\begin{align*}
a&=bq_1+r_1\\
b&=r_1q_2+r_2\\
r_1&=r_2q_3+r_3\\
\cdots\\
r_{n-3}&=r_{n-2}q_{n-1}+r_{n-1}\\
r_{n-2}&=r_{n-1}q_{n}+0
\end{align*}
Then the previous remainder, \(r_{n-1}\), is the greatest common divisor.
First let's see why this even does anything. 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 will be the answer. Another way to think about it is that since \(b\) is finite, there won't be an infinite 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\). All such \(d\) also divide \begin{equation*}a-q_1b=1\cdot a+(-q_1)\cdot b=r_1\end{equation*} So these \(d\) also divides \(r_2=b-q_2r_1\), and indeed divide all the remainders, even \(r_{n-1}=r_{n-3}-q_{n-1}r_{n-2}\). So all common divisors of \(a\) and \(b\) are divisors of \(r_{n-1}\).
On the other hand, 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 so forth. Hence \(d\) divides \(a\) and \(b\).
So the set of common divisors of \(a\) and \(b\) are equal to the set of divisors of \(r_{n-1}\), 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; for the theoretical view, see Exercise 2.5.14. Especially if you can find \(a\) and \(b\) for which the algorithm takes four or five steps, you will gain some insight.
