# Euclid’s algorithm

Euclid’s algorithm^{} describes a procedure for finding the greatest common divisor^{} of two integers.

Suppose $a,b\in \mathbb{Z}$, and without loss of generality, $b>0$, because if $$, then $\mathrm{gcd}(a,b)=\mathrm{gcd}(a,|b|)$, and if $b=0$, then $\mathrm{gcd}(a,b)=|a|$. Put $d:=\mathrm{gcd}(a,b)$.

By the division algorithm for integers, we may find integers $q$ and $r$ such that $a={q}_{0}b+{r}_{0}$ where $$.

Notice that $\mathrm{gcd}(a,b)=\mathrm{gcd}(b,{r}_{0})$, because $d\mid a$ and $d\mid b$, so $d\mid {r}_{0}=a-{q}_{0}b$ and
if $b$ and ${r}_{0}$ had a common divisor^{} ${d}^{\prime}$ larger than $d$, then ${d}^{\prime}$ would also be a common divisor of
$a$ and $b$, contradicting $d$’s maximality. Thus, $d=\mathrm{gcd}(b,{r}_{0})$.

So we may repeat the division, this time with $b$ and ${r}_{0}$. Proceeding recursively, we obtain

$a$ | $=$ | $$ | ||

$b$ | $=$ | $$ | ||

${r}_{0}$ | $=$ | $$ | ||

${r}_{1}$ | $=$ | $$ | ||

$\mathrm{\vdots}$ |

Thus we obtain a decreasing sequence of nonnegative integers $b>{r}_{0}>{r}_{1}>{r}_{2}>\mathrm{\dots}$, which
must eventually^{} reach zero, that is to say,
${r}_{n}=0$ for some $n$, and the algorithm terminates. We may easily generalize the previous
argument to show that $d=\mathrm{gcd}({r}_{k-1},{r}_{k})=\mathrm{gcd}({r}_{k},{r}_{k+1})$ for $k=0,1,2,\mathrm{\dots}$,
where ${r}_{-1}=b$. Therefore,

$$d=\mathrm{gcd}({r}_{n-1},{r}_{n})=\mathrm{gcd}({r}_{n-1},0)={r}_{n-1}.$$ |

More 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
combination^{} of $a$ and $b$, a fact obscurely known as Bezout’s lemma. For we have that

$a-{q}_{0}b$ | $=$ | ${r}_{0}$ | ||

$b-{q}_{1}{r}_{0}$ | $=$ | ${r}_{1}$ | ||

${r}_{0}-{q}_{2}{r}_{1}$ | $=$ | ${r}_{2}$ | ||

${r}_{1}-{q}_{3}{r}_{2}$ | $=$ | ${r}_{3}$ | ||

$\mathrm{\vdots}$ | ||||

${r}_{n-3}-{q}_{n-1}{r}_{n-2}$ | $=$ | ${r}_{n-1}$ | ||

${r}_{n-2}$ | $=$ | ${q}_{n}{r}_{n-1}$ |

so substituting each remainder ${r}_{k}$ into the next equation we obtain

$$\begin{array}{ccccc}\hfill b-{q}_{1}(a-{q}_{0}b)\hfill & \hfill =\hfill & \hfill {k}_{1}a+{l}_{1}b\hfill & \hfill =\hfill & \hfill {r}_{1}\hfill \\ \hfill (a-{q}_{0}b)-{q}_{2}({k}_{1}a+{l}_{1}b)\hfill & \hfill =\hfill & \hfill {k}_{2}a+{l}_{2}b\hfill & \hfill =\hfill & \hfill {r}_{2}\hfill \\ \hfill ({k}_{1}a+{l}_{1}b)-{q}_{3}({k}_{2}a+{l}_{2}b)\hfill & \hfill =\hfill & \hfill {k}_{3}a+{l}_{3}b\hfill & \hfill =\hfill & \hfill {r}_{3}\hfill \\ & \hfill \mathrm{\vdots}\hfill & & \hfill \mathrm{\vdots}\hfill & \\ \hfill ({k}_{n-3}a+{l}_{n-3}b)-{q}_{n}({k}_{n-2}a+{l}_{n-2}b)\hfill & \hfill =\hfill & \hfill {k}_{n-1}a+{l}_{n-1}b\hfill & \hfill =\hfill & \hfill {r}_{n-1}\hfill \end{array}$$ |

Sometimes, especially for manual computations, it is preferable 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
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
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.

$$\begin{array}{cccc}\hfill r\hfill & \hfill q\hfill & \hfill k\hfill & \hfill l\hfill \\ \hfill 756\hfill & & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 595\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 161\hfill & \hfill 3\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 112\hfill & \hfill 1\hfill & \hfill -3\hfill & \hfill 4\hfill \\ \hfill 49\hfill & \hfill 2\hfill & \hfill 4\hfill & \hfill -5\hfill \\ \hfill 14\hfill & \hfill 3\hfill & \hfill -11\hfill & \hfill 14\hfill \\ \hfill 7\hfill & \hfill 2\hfill & \hfill 37\hfill & \hfill -47\hfill \\ \hfill 0\hfill & & & \end{array}$$ |

Thus, $gcd(756,595)=7$ and $37\cdot 756-47\cdot 595=7$.

Euclid’s algorithm was first described in his classic work Elements (see propositions^{} VII 1 and VII 2),
which also contained procedures
for geometrical constructions. These are the first known
formally described algorithms. Prior to this, informally defined algorithms were in common use to
perform various computations, but Elements contained the first attempt to rigorously
describe a procedure and explain why its results are admissible^{}. Euclid’s algorithm for greatest
common divisor is still commonly used today; since Elements was published in the fourth
century BC, this algorithm has been in use for nearly 2400 years!

Title | Euclid’s algorithm |
---|---|

Canonical name | EuclidsAlgorithm |

Date of creation | 2013-03-22 12:00:04 |

Last modified on | 2013-03-22 12:00:04 |

Owner | rmilson (146) |

Last modified by | rmilson (146) |

Numerical id | 21 |

Author | rmilson (146) |

Entry type | Algorithm |

Classification | msc 11A05 |

Synonym | Euclidean algorithm^{} |

Related topic | BezoutsLemma |

Related topic | EuclideanRing |