3.5: The Euclidean Algorithm

Definitions: common divisor

Let $a$ and $b$ be integers, not both 0. A common divisor of $a$ and $b$ is any nonzero integer that divides both $a$ and $b$. The largest natural number that divides both $a$ and $b$ is called the greatest common divisor of $a$ and $b$. The greatest common divisor of $a$ and $b$ is denoted by gcd($a$, $b$)

Preview Activity $\PageIndex{1}$: The GCD and the Division Algorithm

When we speak of the quotient and the remainder when we “divide an integer $a$ by the positive integer $b$,” we will always mean the quotient $q$ and the remainder $r$ guaranteed by the Quotient Remainder Theorem.

1. Each row in the following table contains values for the integers $a$ and $b$. In this table, the value of $r$ is the remainder (from the Division Algorithm) when $a$ is divided by $b$. Complete each row in this table by determining gcd($a$, $b$), $r$, and gcd($b, r$).

   $a$	$b$	gcd($a$, $b$)	Remainder $r$	gcd($b$, $r$)
   44	12
   75	21
   50	33

2. Formulate a conjecture based on the results of the table in Part (1).

We have already studied a good deal of number theory in this text in our discussion of proof methods. In particular, we have studied even and odd integers, divisibility of integers, and the Quotient-Remainder Theorem. 

Before we develop an efficient method for determining the greatest common divisor of two integers, we need to establish some properties of greatest common divisors.

 

Lemma 3.5.1

Let $a, b \in \mathbb{Z}$ with $b > 0$. Then  gcd(0, $b$) = $b$.

 

Lemma 3.5.2

Let $c$ and $d$ be integers, not both equal to zero. If $q$ and $r$ are integers such that $c = d \cdot q + r$, then gcd($c$, $d$) = gcd($d$, $r$).

Proof

Let $c$ and $d$ be integers, not both equal to zero. Assume that $q$ and $r$ are integers such that $c = d \cdot q + r$. For ease of notation, we will let

$m =$ gcd($c$, $d$) and $n =$ gcd($d$, $r$).

Now, $m$ divides $c$ and $m$ divides $d$. Consequently, there exist integers $x$ and $y$ such that $c = mx$ and $d = my$. Hence,

$$\begin{array} {rcl} {r} &= & {c - d \cdot q} \\ {r} &= & {mx - (my)q} \\ {r} &= & {m(x - yq).} \end{array}$$

But this means that $m$ divides $r$. Since m divides $d$ and $m$ divides $r$, $m$ is less than or equal to gcd($d$, $r$). Thus, $m \le n$.

Using a similar argument, we see that $n$ divides $d$ and $n$ divides $r$. Since $c = d \cdot q + r$, we can prove that $n$ divides $c$. Hence, $n$ divides $c$ and $n$ divides $d$. Thus, $n \le$ gcd($c$, $d$) or $n \le m$. We now have $m \le n$ and $n \le m$. Hence, $m = n$ and gcd($c$, $d$) = gcd($d$, $r$).

Progress Check 3.5.1: Illustrations of Lemma 3.5.2

We completed several examples illustrating Lemma 8.1 in Preview Activity $\PageIndex{1}$. For another example, let $c = 56$ and $d = 12$. The greatest common divisor of 56 and 12 is 4.

1. According to the Division Algorithm, what is the remainder $r$ when 56 is divided by 12?

2. What is the greatest common divisor of 12 and the remainder $r$?
   
   The key to finding the greatest common divisor (in more complicated cases) is to use the Division Algorithm again, this time with 12 and $r$. We now find integers $q_2$ and $r_2$ such that
   $$12 = r \cdot q_2 + r_2.$$

3. What is the greatest common divisor of $r$ and $r_2$?

Answer

(1) 8
(2) 4; 12 = 8(1) +4
(3) 4

The Euclidean Algorithm

The example in Progress Check 8.2 illustrates the main idea of the Euclidean Algorithm for finding gcd($a$, $b$), which is explained in the proof of the following theorem.

Theorem 3.5.1: Euclidean Algorithm

Let $a$ and $b$ be integers with $a>b \geq 0$. Then gcd($a$, $b$) is the only natural number $d$ such that

(a) $d$ divides $a$ and $d$ divides $b$, and
(b) if $k$ is an integer that divides both $a$ and $b$, then $k$ divides $d$.

Note: if $b=0$ then the gcd($a$, $b$)=$a$, by Lemma 3.5.1.

Proof

Let $a$ and $b$ be integers with $a>b \geq 0$, and let $d =$ gcd($a$, $b$). By the Quotient Remainder Theorem, there exist integers $q_1$ and $r_1$ such that

$$a = b \cdot q_1 + r_1 \text{, and } 0 \le r_1 < b.$$

If $r_1 = 0$, then equation (8.1.3) implies that $b$ divides $a$. Hence, $b = d =$ gcd($a$, $b$) and this number satisfies Conditions (a) and (b).

If $r_1 > 0$, then by Lemma 8.1, gcd($a$, $b$) = gcd($b$, $r_1$). We use the Division Algorithm again to obtain integers $q_2$ and $r_2$ such that

$$b = r_1 \cdot q_2 + r_2 \text{, and } 0 \le r_2 < r_1.$$

If $r_2 = 0$, then equation (8.1.4) implies that $r_1$ divides $b$. This means that $r_1 =$ gcd($b$, $r_1$). But we have already seen that gcd($a$, $b$) = gcd($b$, $r_1$). Hence, $r_1 =$ gcd($a$, $b$). In addition, if $k$ is an integer that divides both $a$ and $b$, then, using equation (8.1.3), we see that $r_1 = a - b \cdot q_1$ and, hence $k$ divides $r_1$. This shows that $r_1 =$ gcd($a$, $b$) satisfies Conditions (a) and (b).

If $r_2 > 0$, then by Lemma 8.1, gcd($b$, $r_1$) = gcd($r_1$, $r_2$). But we have already seen that gcd($a$, $b$) = gcd($b$, $r_1$). Hence, gcd($a$, $b$) = gcd($r_1$, $r_2$). We now continue to apply the Division Algorithm to produce a sequence of pairs of integers (all of which have the same greatest common divisor). This is summarized in the following table:

Original Pair	Equation from Division	Inequality from Division Algorithm	New Pair
($a, b$)	$a = b \cdot q_1 + r_1$	$0 \le r_1 < b$	($b, r_1$)
($b, r_1$)	$b = r_1 \cdot q_2 + r_2$	$0 \le r_2 < r_1$	($r_1, r_2$)
($r_1, r_2$)	$r_1 = r_2 \cdot q_1 + r_3$	$0 \le r_3 < r_2$	($r_2, r_3$)
($r_2, r_3$)	$r_2 = r_3 \cdot q_1 + r_4$	$0 \le r_4 < r_3$	($r_3, r_4$)
($r_3, r_4$)	$r_3 = r_4 \cdot q_1 + r_5$	$0 \le r_5 < r_4$	($r_4, r_5$)
...	...	...	...

From the inequalities in the third column of this table, we have a strictly decreasing sequence of nonnegative integers ($b > r_1 > r_2 > r_3 > r_4 \cdot\cdot\cdot$). Consequently, a term in this sequence must eventually be equal to zero. Let $p$ be the smallest natural number such that $r_{p + 1} = 0$. This means that the last two rows in the preceding table will be

Original Pair	Equation from Division Algorithm	Inequality from Division Algorithm	New Pair
($r_{p - 2}, r_{p - 1}$)	$r_{p - 2} = r_{p - 1} \cdot q_{p} + r_p$	$0 \le r_{p} < r_{p - 1}$	($r_{p - 1}, r_{p}$)
($r_{p - 1}, r_{p}$)	$r_{p - 1} = r_{p} \cdot q_{p + 1} + 0$

Remember that this table was constructed by repeated use of Lemma 8.1 and that the greatest common divisor of each pair of integers produced equals gcd($a$, $b$). Also, the last row in the table indicates that $r_{p}$ divides $r_{p - 1}$. This means that gcd($r_{p - 1}, r_{p}$) $= r_{p}$ and hence $r_p =$ gcd($a$, $b$).

This proves that $r_p =$ gcd($a$, $b$) satisfies Condition (a) of this theorem. Now assume that $k$ is an integer such that $k$ divides $a$ and $k$ divides $b$. We proceed through the table row by row. First, since $r_1 = a - b \cdot q$, we see that

$k$ must divide $r_1$.

The second row tells us that $r_2 = b - r_{1} \cdot q_{2}$. Since $k$ divides $b$ and $k$ divides $r_1$, we conclude that

$k$ divides $r_2$.

Continuing with each row, we see that $k$ divides each of the remainders $r_1, r_2, r_3, ..., r_{p}$. This means that $r_p =$ gcd($a$, $b$) satisfies Condition (b) of the theorem.

 

Example $\PageIndex{1}$: (Using the Euclidean Algorithm)

Let $a = 234$ and $b = -42$. We will use the Euclidean Algorithm to determine gcd(234, 42).

Step	Original Pair	Equation from Division Algorithm	New Pair
1	(234, 42)	$234 = 42 \cdot 5 + 24$	(42, 24)
2	(42, 24)	$42 = 24 \cdot 1 + 18$	(24, 18)
3	(24, 18)	$24 = 18 \cdot 1 + 6$	(18, 6)
4	(18, 6)	$18 = 6 \cdot 3$

So gcd(234, 42) = 6 and hence gcd(234, -42) = 6.

Exercises

Exercise $\PageIndex{1}$:

1. Find each of the following greatest common divisors by using the Euclidean Algorithm.

(a) gcd(21, 2511)              (b) gcd(110, 2511)                 (c) gcd(509,1177)
 

2. Find each of the following greatest common divisors by using the Euclidean Algorithm.
(a) gcd(10933, 832)          (b) gcd(1265,18400)
 

3. Let $a,b \in \mathbb{Z}^+$ find
(a)   gcd(a,1)     (b) gcd(a,a)     (c)   gcd(a,0) if $a>0$      (d) gcd(a,35) if $a=35b+14$

Answer:

(a) 1 (b) a (c) a (d) 7

 

4. Disprove mod is distributive over multiplication for the set $\mathbb{Z}^+$, i.e.  using  $a,b,c \in \mathbb{Z}^+$.