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 $b<0$ , then $\gcd(a,b)=\gcd(a,|b|)$ , and if $b=0$ , then $\gcd(a,b)=|a|$ . Put $d:=\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 $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_{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=\gcd(b,r_{0})$ .

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

$\displaystyle a$	$\displaystyle=$	$\displaystyle q_{0}b+r_{0}~{}\mbox{ with }0\leq r_{0}<b$
$\displaystyle b$	$\displaystyle=$	$\displaystyle q_{1}r_{0}+r_{1}\mbox{ with }0\leq r_{1}<r_{0}$
$\displaystyle r_{0}$	$\displaystyle=$	$\displaystyle q_{2}r_{1}+r_{2}\mbox{ with }0\leq r_{2}<r_{1}$
$\displaystyle r_{1}$	$\displaystyle=$	$\displaystyle q_{3}r_{2}+r_{3}\mbox{ with }0\leq r_{3}<r_{2}$
	$\displaystyle\vdots$

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, $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$ , 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.

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

$\displaystyle a-q_{0}b$	$\displaystyle=$	$\displaystyle r_{0}$
$\displaystyle b-q_{1}r_{0}$	$\displaystyle=$	$\displaystyle r_{1}$
$\displaystyle r_{0}-q_{2}r_{1}$	$\displaystyle=$	$\displaystyle r_{2}$
$\displaystyle r_{1}-q_{3}r_{2}$	$\displaystyle=$	$\displaystyle r_{3}$
	$\displaystyle\vdots$
$\displaystyle r_{n-3}-q_{n-1}r_{n-2}$	$\displaystyle=$	$\displaystyle r_{n-1}$
$\displaystyle r_{n-2}$	$\displaystyle=$	$\displaystyle q_{n}r_{n-1}$

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

$\begin{array}[]{ccccc}b-q_{1}(a-q_{0}b)&=&k_{1}a+l_{1}b&=&r_{1}\\ (a-q_{0}b)-q_{2}(k_{1}a+l_{1}b)&=&k_{2}a+l_{2}b&=&r_{2}\\ (k_{1}a+l_{1}b)-q_{3}(k_{2}a+l_{2}b)&=&k_{3}a+l_{3}b&=&r_{3}\\ &\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}\\ \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}[]{c@{~\vline~}c@{~\vline~}c@{~\vline~}c}r~{}~{}&q~{}~{}&k~{}~{}&% l\\ \hline 756~{}~{}&~{}~{}&1~{}~{}&0\\ 595~{}~{}&1~{}~{}&0~{}~{}&1\\ 161~{}~{}&3~{}~{}&1~{}~{}&-1\\ 112~{}~{}&1~{}~{}&-3~{}~{}&4\\ 49~{}~{}&2~{}~{}&4~{}~{}&-5\\ 14~{}~{}&3~{}~{}&-11~{}~{}&14\\ 7~{}~{}&2~{}~{}&37~{}~{}&-47\\ 0~{}~{}&~{}~{}&~{}~{}&\\ ~{}~{}\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