| Version 13 |
Version 12 |
| Euclid's algorithm describes a procedure for finding the greatest common divisor of two integers. |
Euclid's algorithm describes a procedure for finding the greatest common divisor of two integers. |
| Suppose $a,~b \in \ZZ$, and without loss of generality, $b > 0$, because if $b < 0$, |
Suppose $a,~b \in \ZZ$, and without loss of generality, $b > 0$, because if $b < 0$, |
| then $\gcd(a,b) = \gcd (a, |b| )$, and if $b = 0$, then $\gcd (a,b) = |a| $. |
then $\gcd(a,b) = \gcd (a, |b| )$, and if $b = 0$, then $\gcd (a,b) = |a| $. |
| Put $d := \gcd (a,b)$. |
Put $d := \gcd (a,b)$. |
| By the division algorithm for integers, we may find integers $q$ and $r$ such that |
By the division algorithm for integers, we may find integers $q$ and $r$ such that |
| $a = q_0 b + r_0 $ where $ 0 \leq r_0 < b$. |
$a = q_0 b + r_0 $ where $ 0 \leq r_0 < b$. |
| Notice that $\gcd(a,b) = \gcd(b, r_0)$, because $d \mid a$ and $d \mid b$, so $d \mid r_0 = a - q_0b$ and |
Notice that $\gcd(a,b) = \gcd(b, r_0)$, because $d \mid a$ and $d \mid b$, so $d \mid r_0 = a - q_0b$ and |
| if $b$ and $r_0$ had a common divisor $d'$ larger than $d$, then $d'$ would also be a common divisor of |
if $b$ and $r_0$ had a common divisor $d'$ larger than $d$, then $d'$ would also be a common divisor of |
| $a$ and $b$, contradicting $d$'s maximality. Thus, $d = \gcd(b, r_0)$. |
$a$ and $b$, contradicting $d$'s maximality. Thus, $d = \gcd(b, r_0)$. |
| So we may repeat the division, this time with $b$ and $r_0$. Proceeding recursively, we obtain |
So we may repeat the division, this time with $b$ and $r_0$. Proceeding recursively, we obtain |
| \begin{eqnarray*} |
\begin{eqnarray*} |
| a &=& q_0b + r_0 ~\mbox{ with } 0 \leq r_0 < b \\ |
a &=& q_0b + r_0 ~\mbox{ with } 0 \leq r_0 < b \\ |
| b &=& q_1r_0 + r_1 \mbox{ with } 0 \leq r_1 < r_0 \\ |
b &=& q_1r_0 + r_1 \mbox{ with } 0 \leq r_1 < r_0 \\ |
| r_0 &=& q_2r_1 + r_2 \mbox{ with } 0 \leq r_2 < r_1 \\ |
r_0 &=& q_2r_1 + r_2 \mbox{ with } 0 \leq r_2 < r_1 \\ |
| r_1 &=& q_3r_2 + r_3 \mbox{ with } 0 \leq r_3 < r_2 \\ |
r_1 &=& q_3r_2 + r_3 \mbox{ with } 0 \leq r_3 < r_2 \\ |
| &\vdots& |
&\vdots& |
| \end{eqnarray*} |
\end{eqnarray*} |
| Thus we obtain a decreasing sequence of nonnegative integers $b > r_0 > r_1 > r_2 > \dots$, which |
Thus we obtain a decreasing sequence of nonnegative integers $b > r_0 > r_1 > r_2 > \dots$, which |
| must eventually reach zero, that is to say, |
must eventually reach zero, that is to say, |
| $r_n = 0$ for some $n$, and the algorithm terminates. We may easily generalize the previous |
$r_n = 0$ for some $n$, and the algorithm terminates. We may easily generalize the previous |
| argument to show that $d = \gcd(r_{k-1}, r_k) = \gcd(r_k, r_{k+1})$ for $k = 0, 1, 2, \dots$, |
argument to show that $d = \gcd(r_{k-1}, r_k) = \gcd(r_k, r_{k+1})$ for $k = 0, 1, 2, \dots$, |
| where $r_{-1} = b$. Therefore, \[d = \gcd(r_{n-1}, r_n) = \gcd(r_{n-1}, 0) = r_{n-1}.\] More |
where $r_{-1} = b$. Therefore, \[d = \gcd(r_{n-1}, r_n) = \gcd(r_{n-1}, 0) = r_{n-1}.\] More |
| colloquially, the greatest common divisor is the last nonzero remainder in the algorithm. |
colloquially, the greatest common divisor is the last nonzero remainder in the algorithm. |
| The algorithm provides a bit more than this. It also yields a way to express the $d$ as a linear |
The algorithm provides a bit more than this. It also yields a way to express the $d$ as a linear |
| combination of $a$ and $b$, a fact obscurely known as Bezout's lemma. For we have that |
combination of $a$ and $b$, a fact obscurely known as Bezout's lemma. For we have that |
| \begin{eqnarray*} |
\begin{eqnarray*} |
| a -q_0b &=& r_0 \\ |
a -q_0b &=& r_0 \\ |
| b -q_1r_0 &=& r_1 \\ |
b -q_1r_0 &=& r_1 \\ |
| r_0 - q_2r_1 &=& r_2 \\ |
r_0 - q_2r_1 &=& r_2 \\ |
| r_1 - q_3r_2 &=& r_3 \\ |
r_1 - q_3r_2 &=& r_3 \\ |
| &\vdots& \\ |
&\vdots& \\ |
| r_{n-3} - q_{n-1}r_{n-2} &=& r_{n-1} \\ |
r_{n-3} - q_{n-1}r_{n-2} &=& r_{n-1} \\ |
| r_{n-2} &=& q_nr_{n-1} \\ |
r_{n-2} &=& q_nr_{n-1} \\ |
| \end{eqnarray*} |
\end{eqnarray*} |
| so substituting each remainder $r_k$ into the next equation we obtain |
so substituting each remainder $r_k$ into the next equation we obtain |
| \begin{table}[ht] |
\begin{table}[ht] |
| \begin{array}{ccccc} |
\begin{array}{ccccc} |
| b - q_1(a - q_0b) &=& k_1a + l_1b &=& r_1 \\ |
b - q_1(a - q_0b) &=& k_1a + l_1b &=& r_1 \\ |
| (a - q_0b) - q_2(k_1a + l_1b) &=& k_2a + l_2b &=& r_2 \\ |
(a - q_0b) - q_2(k_1a + l_1b) &=& k_2a + l_2b &=& r_2 \\ |
| (k_1a + l_1b) - q_3(k_2a + l_2b) &=& k_3a + l_3b &=& r_3 \\ |
(k_1a + l_1b) - q_3(k_2a + l_2b) &=& k_3a + l_3b &=& r_3 \\ |
| &\vdots & &\vdots& \\ |
&\vdots & &\vdots& \\ |
| (k_{n-3}a + l_{n-3}b) - q_n(k_{n-2}a + l_{n-2}b) &=& k_{n-1} a + l_{n-1} b &=& r_{n-1} \\ |
(k_{n-3}a + l_{n-3}b) - q_n(k_{n-2}a + l_{n-2}b) &=& k_{n-1} a + l_{n-1} b &=& r_{n-1} \\ |
| \end{array} |
\end{array} |
| \end{table} |
\end{table} |
| Sometimes, especially for manual computations, it is preferrable to write all the algorithm in a tabular |
Sometimes, especially for manual computations, it is preferrable to write all the algorithm in a tabular |
| format. As an example, let us apply the algorithm to $a=756$ and $b=595$. The following table details |
format. As an example, let us apply the algorithm to $a=756$ and $b=595$. The following table details |
| the procedure. The variables at the top of each column (without subscripts) have the same meaning as above. |
the procedure. The variables at the top of each column (without subscripts) have the same meaning as above. |
| That is to say, $r$ is used for the sequence of remainders and $q$ for the corresponding sequence of |
That is to say, $r$ is used for the sequence of remainders and $q$ for the corresponding sequence of |
| quotients. The entries in the $k$ and $l$ columns are obtained by multiplying the current values for $k$ |
quotients. The entries in the $k$ and $l$ columns are obtained by multiplying the current values for $k$ |
| and $l$ by the $q$ in this row, and subtracting the results from the $k$ and $l$ in the previous row. |
and $l$ by the $q$ in this row, and subtracting the results from the $k$ and $l$ in the previous row. |
| \begin{table}[h] |
\begin{table}[h] |
| \begin{array}{c@{~\vline~}c@{~\vline~}c@{~\vline~}c} |
\begin{array}{c@{~\vline~}c@{~\vline~}c@{~\vline~}c} |
| r & q & k & l \\ |
r & q & k & l \\ |
| \hline |
\hline |
| 756 & & 1 & 0 \\ |
756 & & 1 & 0 \\ |
| 595 & 1 & 0 & 1 \\ |
595 & 1 & 0 & 1 \\ |
| 161 & 3 & 1 & -1 \\ |
161 & 3 & 1 & -1 \\ |
| 112 & 1 & -3 & 4 \\ |
112 & 1 & -3 & 4 \\ |
| 49 & 2 & 4 & -5 \\ |
49 & 2 & 4 & -5 \\ |
| 14 & 3 & -11 & 14 \\ |
14 & 3 & -11 & 14 \\ |
| 7 & 2 & 37 & -47 \\ |
7 & 2 & 37 & -47 \\ |
| 0 & & & \\ |
0 & & & \\ |
| \end{array} |
\end{array} |
| \end{table} |
\end{table} |
| Thus, $gcd(756, 595) = 7$ and $37 \cdot 756 - 47 \cdot 595 = 7$. |
Thus, $gcd(756, 595) = 7$ and $37 \cdot 756 - 47 \cdot 595 = 7$. |
| Euclid's algorithm was first described in his classic work {\it Elements}, which also contained procedures |
Euclid's algorithm was first described in his classic work {\it Elements}, which also contained procedures |
| for geometrical constructions. These are the first known |
for geometrical constructions. These are the first known |
| formally described algorithms. Prior to this, informally defined algorithms were in common use to |
formally described algorithms. Prior to this, informally defined algorithms were in common use to |
| perform various computations, but {\it Elements} contained the first attempt to rigorously |
perform various computations, but {\it Elements} contained the first attempt to rigorously |
| describe a procedure and explain why its results are admissable. Euclid's algorithm for greatest |
describe a procedure and explain why its results are admissable. Euclid's algorithm for greatest |
| common divisor is still commonly used today; since {\it Elements} was published in the fourth |
common divisor is still commonly used today; since {\it Elements} was published in the fourth |
| century BC, this algorithm has been in use for nearly 2400 years! |
century BC, this algorithm has been in use for nearly 2400 years! |
|
(More to come on algorithmic complexity!) |
