In this section we introduce the so-called Division algorithm, we define the greatest common divisor of given integers and we consider the Euclidean algorithm, which is one of the oldest mathematical algorithms.
Division algorithm. Given two integers \(a\) and \(b\) such that \(b>0\text{.}\) There exist unique integers \(q\) and \(r\) for which
\begin{equation*} a=qb+r, 0\leq r\lt b\text{.} \end{equation*}Here \(q\) is called quotient and \(r\) is called remainder. There is a special case, when the Division algorithm yields \(r=0\text{.}\) In such a situation \(a=qb\) for some \(q\text{.}\)
We say that \(b\) divides \(a\) (\(b\) is a divisor of \(a\) or \(a\) is a multiple of \(b\)) if there exists \(q\) such that \(a=qb\text{.}\) Notation: \(b\mid a\text{.}\)
How to find an appropriate \(q\) and \(r\text{?}\) Let us assume that we have two positive integers \(a\) and \(b\text{.}\) We start with \(q=0\) and \(r=a\text{.}\) Clearly \(a=0\cdot b+a\text{.}\) If \(a\lt b\text{,}\) then we are done, otherwise \(a-b\geq 0\text{.}\) So we write \(a=1\cdot b+(a-b)\text{.}\) We check if \(a-b\lt b\text{.}\) If this is the case then we have found \(q\) and \(r\text{,}\) otherwise we have \(a-2b\geq 0\) and \(a=2\cdot b+(a-2b)\text{.}\) We stop when we have \(a-kb\lt b\) for some \(k\text{.}\) For example, let \(a=76\) and \(b=7:\)
| \(k\) | \(a-kb\) |
| 0 | 76 |
| 1 | 69 |
| 2 | 62 |
| 3 | 55 |
| 4 | 48 |
| 5 | 41 |
| 6 | 34 |
| 7 | 27 |
| 8 | 20 |
| 9 | 13 |
| 10 | 6 |
that is, we obtain that \(76=10\cdot 7+6\) and \(0\leq 6\lt 7\text{.}\)
Let \(a,b\in\mathbb{Z}\text{.}\) A positive integer \(d\) is called a common divisor of \(a\) and \(b\text{,}\) if \(d\) divides \(a\) and \(d\) divides \(b\text{.}\) The largest possible such integer is called the greatest common divisor of \(a\) and \(b\text{.}\) Notation: \(\gcd(a,b)\text{.}\)
The Euclidean algorithm. Now we study a method to determine \(\gcd(a,b)\) of given positive integers \(a\) and \(b\text{.}\) The method also provides solution of the linear Diophantine equation
\begin{equation*} ax+by=\gcd(a,b)\text{.} \end{equation*}If we apply the Division algorithm to \(a,b,a>b\text{,}\) then we have
\begin{equation*} a=qb+r, 0\leq r\lt b\text{.} \end{equation*}If \(d\) is a common divisor of \(a\) and \(b\text{,}\) then \(d\) divides \(r=a-qb\) as well. That is the basic idea of the algorithm. The Euclidean algorithm works as follows. First we apply the Division algorithm for \(a\) and \(b\) to obtain a quotient \(q_1\) and a remainder \(r_1\text{.}\) Then we apply the Division algorithm for \(b\) and \(r_1\) to get a new quotient \(q_2\) and a new remainder \(r_2\text{.}\) We continue, we divide \(r_1\) by \(r_2\) to obtain \(q_3\) and \(r_3\text{.}\) We stop if we obtain a zero remainder. Since the procedure produces a decreasing sequence of non-negative integers so must eventually terminate by descent. The last non-zero remainder is the greatest common divisor of \(a\) and \(b\text{.}\)
As an example we compute \(\gcd(553,161)\text{.}\) We write the computations in the following way:
\begin{align*} 553\amp =3\cdot 161+70 q_1=3, r_1=70\\ 161\amp =2\cdot 70+21 q_2=2, r_2=21\\ 70\amp =3\cdot 21+7 q_3=3, r_3=7\\ 21\amp =3\cdot 7+0 q_4=3, r_4=0\text{.} \end{align*}That is, the last non-zero remainder is 7, so \(\gcd(553,161)=7\text{.}\) If we would like to express 7 as \(553x+161y\) for some \(x,y\in\mathbb{Z}\text{,}\) we can do it by working backwards
\begin{align*} 7\amp =70-3\cdot 21\\ \amp =70-3\cdot (161-2\cdot 70)=-3\cdot 161+7\cdot 70\\ \amp =-3\cdot 161+7 \cdot (553-3\cdot 161)=7\cdot 553-24\cdot 161\text{.} \end{align*}It follows that \(x=7\) and \(y=-24\text{.}\)
Use the Euclidean algorithm to find \(\gcd(a,b)\) and compute integers \(x\) and \(y\) for which
\begin{equation*} ax+by=\gcd(a,b): \end{equation*}(a) \(a=678, b=567\text{,}\)
(b) \(a=803, b=319\text{,}\)
(c) \(a=2701, b=2257\text{,}\)
(d) \(a=3397, b=1849\text{.}\)