1.6: The Euclidean Algorithm

Last updated
Save as PDF

Page ID: 8822

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

In this section we describe a systematic method that determines the greatest common divisor of two integers. This method is called the Euclidean algorithm.

[lem1] If \(a\) and \(b\) are two integers and \(a=bq+r\) where also \(q\) and \(r\) are integers, then \((a,b)=(r,b)\).

Note that by theorem 8, we have \((bq+r,b)=(b,r)\).

The above lemma will lead to a more general version of it. We now present the Euclidean algorithm in its general form. It states that the greatest common divisor of two integers is the last non zero remainder of the successive division.

Let \(a=r_0\) and \(b=r_1\) be two positive integers where \(a\geq b\). If we apply the division algorithm successively to obtain that \[r_j=r_{j+1}q_{j+1}+r_{j+2} \ \ \mbox{where} \ \ 0\leq r_{j+2}<r_{j+1}\] for all \(j=0,1,...,n-2\) and \[r_{n+1}=0.\] Then \((a,b)=r_{n}\).

By applying the division algorithm, we see that \[\begin{aligned} r_0&=&r_1q_1+r_2 \ \ \ \ \ 0\leq r_2<r_1, \\ r_1&=&r_2q_2+r_3 \ \ \ \ \ 0\leq r_3<r_2, \\ &.& \\ &.& \\ &.& \\ r_{n-2}&=&r_{n-1}q_{n-1}+r_{n} \ \ \ \ \ 0\leq r_{n}<r_{n-1}, \\ r_{n-1}&=&r_{n}q_{n}.\end{aligned}\] Notice that, we will have a remainder of \(0\) eventually since all the remainders are integers and every remainder in the next step is less than the remainder in the previous one. By Lemma [lem1], we see that \[(a,b)=(b,r_2)=(r_2,r_3)=...=(r_n,0)=r_n.\]

We will find the greatest common divisor of \(4147\) and \(10672\):

Note that \[\begin{aligned} 10672&=&4147\cdot 2+2378,\\ 4147&=&2378\cdot 1+1769,\\ 2378&=&1769\cdot 1+609,\\ 1769&=&609\cdot 2 +551,\\ 609&=& 551\cdot 1+58, \\ 551&=&58\cdot 9+ 29,\\ 58&=&29\cdot 2,\\\end{aligned}\] Hence \((4147,10672)=29.\)

We now use the steps in the Euclidean algorithm to write the greatest common divisor of two integers as a linear combination of the two integers. The following example will actually determine the variables \(m\) and \(n\) described in Theorem [thm9]. The following algorithm can be described by a general form but for the sake of simplicity of expressions we will present an example that shows the steps for obtaining the greatest common divisor of two integers as a linear combination of the two integers.

Express 29 as a linear combination of \(4147\) and \(10672\):

\[\begin{aligned} 29&=&551-9\cdot 58,\\ &=& 551-9(609-551\cdot 1),\\ &=& 10.551-9.609,\\ &=& 10\cdot (1769-609\cdot 2)-9\cdot 609,\\ &=& 10\cdot 1769-29\cdot 609,\\ &=& 10\cdot 1769-29(2378-1769\cdot 1),\\ &=& 39\cdot 1769-29\cdot 2378,\\ &=& 39(4147-2378\cdot 1)-29\cdot 2378,\\ &=& 39\cdot 4147-68\cdot 2378,\\ &=& 39\cdot 4147-68(10672-4147\cdot 2),\\ &=& 175\cdot 4147-68\cdot 10672,\end{aligned}\]

As a result, we see that \(29=175\cdot 4147-68\cdot 10672\).

Exercises

Use the Euclidean algorithm to find the greatest common divisor of 412 and 32 and express it in terms of the two integers.
Use the Euclidean algorithm to find the greatest common divisor of 780 and 150 and express it in terms of the two integers.
Find the greatest common divisor of \(70,98, 108\).
Let \(a\) and \(b\) be two positive even integers. Prove that \((a,b)=2(a/2,b/2).\)
Show that if \(a\) and \(b\) are positive integers where \(a\) is even and \(b\) is odd, then \((a,b)=(a/2,b).\)

Contributors and Attributions

Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.