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$ andif $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$ , whichmust eventually reach zero, that is to say, $r_{n}=0$ for some $n$ , and the algorithm terminates. We may easily generalize the previousargument 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}.

Morecolloquially, 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 linearcombination 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 tabularformat. As an example, let us apply the algorithm to $a=756$ and $b=595$ . The following table detailsthe 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 ofquotients. 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 proceduresfor geometrical constructions. These are the first knownformally described algorithms. Prior to this, informally defined algorithms were in common use toperform various computations, but Elements contained the first attempt to rigorouslydescribe a procedure and explain why its results are admissible. Euclid’s algorithm for greatestcommon divisor is still commonly used today; since Elements was published in the fourthcentury BC, this algorithm has been in use for nearly 2400 years!