Section 2.3 The Euclidean Algorithm
The Euclidean algorithm says that to find the gcd of \(a\) and \(b\text{,}\) one performs the division algorithm until zero is the remainder, each time replacing the previous divisor by the previous remainder, and the previous number to be divided (sometimes called dividend) by the previous divisor. The last non-zero remainder is the gcd.
We’ll state and prove this momentarily (
Algorithm 2.3.3). Let’s try it with a reasonably sized problem.
Example 2.3.1.
Let \(a=60\) and \(b=42\text{.}\)
\begin{align*}
60&=42\cdot 1+18\\
42&=18\cdot 2+6\\
18&=6\cdot 3+0
\end{align*}
So \(\gcd(60,42)=6\text{.}\)
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.
Algorithm 2.3.3. Euclidean algorithm.
To get the greatest common divisor of \(a\) and \(b\text{,}\) 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}\text{,}\) is the greatest common divisor.
Proof.
First let’s see why this algorithm even terminates. 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. 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\text{.}\) 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 divide \(r_2=b-q_2r_1\text{,}\) and indeed divide all the remainders, even \(r_{n-1}=r_{n-3}-q_{n-1}r_{n-2}\text{.}\) So all common divisors of \(a\) and \(b\) are divisors of \(r_{n-1}\text{.}\)
On the other hand, if \(d\) divides \(r_{n-1}\text{,}\) it divides \(r_{n-2}=r_{n-1}q_{n}\text{,}\) and thus divides \(r_{n-3}=r_{n-2}q_{n-1}+r_{n-1}\text{,}\) and so forth. Hence \(d\) divides \(a\) and \(b\text{.}\)
So the set of common divisors of \(a\) and \(b\) are equal to the set of divisors of \(r_{n-1}\text{,}\) 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.
aleph0.clarku.edu/~djoyce/java/elements/bookVII/propVII2.html
aleph0.clarku.edu/~djoyce/java/elements
books.google.com/books?id=rEUMAAAAYAAJ