The Greatest Common Divisor

Section 8.1 The Greatest Common Divisor

Beginning Activity Beginning Activity 1: The Greatest Common Divisor
A4 US

1.

Explain what it means to say that a nonzero integer $m$ divides an integer $n .$ Recall that we use the notation $m ∣ n$ to indicate that the nonzero integer $m$ divides the integer $n .$

🔗

2.

Let $m$ and $n$ be integers with $m \neq 0 .$ Explain what it means to say that $m$ does not divide $n .$

🔗

Definition.

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

🔗

3.

Use the roster method to list the elements of the set that contains all the natural numbers that are divisors of 48.

🔗

4.

Use the roster method to list the elements of the set that contains all the natural numbers that are divisors of 84.

🔗

5.

Determine the intersection of the two sets in Exercise 3 and Exercise 4. This set contains all the natural numbers that are common divisors of 48 and 84.

🔗

6.

What is the greatest common divisor of 48 and 84?

🔗

7.

Use the method suggested in Exercise 3 through Exercise 6 to determine each of the following: $gcd (8, - 12),$ $gcd (0, 5),$ $gcd (8, 27),$ and $gcd (14, 28) .$

🔗

8.

If $a$ and $b$ are integers, make a conjecture about how the common divisors of $a$ and $b$ are related to the greatest common divisor of $a$ and $b .$

🔗

Beginning Activity Beginning Acivity 2: The GCD and the Division Algorithm
A4 US

🔗

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 Division Algorithm. (See Section 3.5, The Division Algorithm.)

🔗

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 Exercise 1.

🔗

Subsection The System of Integers

🔗

Number theory is a study of the system of integers, which consists of the set of integers,

Z = {\dots, - 3, - 2, - 1, 0, 1, 2, 3, \dots}

and the various properties of this set under the usual operations of addition and multiplication and under the usual ordering relation of “less than.” The properties of the integers in Table 8.1 will be considered axioms in this text.

🔗

We will also assume the properties of the integers shown in Table 8.2. These properties can be proven from the properties in Table 8.1. (However, we will not do so here.)

🔗

Table 8.1. Axioms for the Integers

	For all integers $a, b,$ and $c :$
Closure Proporties for Addition and Multiplication	$a + b \in Z$ and $a b \in Z$
Commutative Properties for Addition and Multiplication	$a + b = b + a,$ and $a b = b a$
Associative Properties for Addition and Multiplication	$(a + b) + c = a + (b + c)$ and $(a b) c = a (b c)$
Distributive Properties of Multiplication over Addition	$a (b + c) = a b + a c,$ and $(b + c) a = b a + c a$
Additive and Multiplicative Identity Properties	$a + 0 = 0 + a = a,$ and $a \cdot 1 = 1 \cdot a = a$
Additive Inverse Property	$a + (- a) = (- a) + a = 0$

🔗

Table 8.2. Properties of the Integers

Zero Property of Multiplication	If $a \in Z,$ then $a \cdot 0 = 0 \cdot a = 0 .$
Cancellation Properties of Addition and Multiplication	If $a, b, c \in Z$ and $a + b = a + c,$ then $b = c .$ If $a, b, c \in Z,$ $a \neq 0$ and $a c = b c,$ then $b = c .$

🔗

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, congruence, and the Division Algorithm. See the summary Section 3.7 for a summary of results concerning even and odd integers as well as results concerning properties of divisors. We reviewed some of these properties and the Division Algorithm in the beginning activities.

🔗

Subsection The Greatest Common Divisor

🔗

One of the most important concepts in elementary number theory is that of the greatest common divisor of two integers. The definition for the greatest common divisor of two integers (not both zero) was given in Beginning Activity 1.

If $a, b \in Z$ and $a$ and $b$ are not both 0, and if $d \in N,$ then $d = gcd (a, b)$ provided that it satisfies all of the following properties:
- $d ∣ a$ and $d ∣ b .$ That is, $d$ is a common divisor of $a$ and $b .$
- If $k$ is a natural number such that $k ∣ a$ and $k ∣ b,$ then $k \leq d .$ That is, any other common divisor of $a$ and $b$ is less than or equal to $d .$
Consequently, a natural number $d$ is not the greatest common divisor of $a$ and $b$ provided that it does not satisfy at least one of these properties. That is, $d$ is not equal to $gcd (a, b)$ provided that
- $d$ does not divide $a$ or $d$ does not divide $b;$ or
- There exists a natural number $k$ such that $k ∣ a$ and $k ∣ b$ and $k > d .$
This means that $d$ is not the greatest common divisor of $a$ and $b$ provided that it is not a common divisor of $a$ and $b$ or that there exists a common divisor of $a$ and $b$ that is greater than $d .$

🔗

In the beginning activities, we determined the greatest common divisors for several pairs of integers. The process we used was to list all the divisors of both integers, then list all the common divisors of both integers and, finally, from the list of all common divisors, find the greatest (largest) common divisor. This method works reasonably well for small integers but can get quite cumbersome if the integers are large. 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.

🔗

One property was suggested in Beginning Activity 1. If we look at the results in Exercise 7 of that beginning activity, we should observe that any common divisor of

a

and

b

will divide

gcd (a, b) .

In fact, the primary goals of the remainder of this section are

To find an efficient method for determining $gcd (a, b),$ where $a$ and $b$ are integers.
To prove that the natural number $gcd (a, b)$ is the only natural number $d$ that satisfies the following properties:
- $d$ divides $a$ and $d$ divides $b;$ and
- if $k$ is a natural number such that $k ∣ a$ and $k ∣ b,$ then $k ∣ d .$

🔗

The second goal is only slightly different from the definition of the greatest common divisor. The only difference is in the second condition where

k \leq d

is replaced by

k ∣ d .

🔗

We will first consider the case where

a

and

b

are integers with

a \neq 0

and

b > 0 .

The proof of the result stated in the second goal contains a method (called the Euclidean Algorithm) for determining the greatest common divisor of the two integers

a

and

b .

The main idea of the method is to keep replacing the pair of integers

(a, b)

with another pair of integers

(b, r),

where

0 \leq r < b

and

gcd (b, r) = gcd (a, b) .

This idea was explored in Beginning Activity 2. Lemma 8.3 is a conjecture that could have been formulated in Beginning Activity 2.

🔗

Lemma 8.3.

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 = m x$ and $d = m y .$ Hence,

\begin{aligned} r & = c - d \cdot q \\ r & = m x - (m y) q \\ r & = m (x - y q) . \end{aligned}

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 \leq 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 \leq gcd (c, d)$ or $n \leq m .$ We now have $m \leq n$ and $n \leq m .$ Hence, $m = n$ and $gcd (c, d) = gcd (d, r) .$

🔗

Progress Check 8.4. Illustrations of Lemma 8.3.

We completed several examples illustrating Lemma 8.3 in Beginning Activity 2. For another example, let $c = 56$ and $d = 12 .$ The greatest common divisor of 56 and 12 is 4.

🔗

(a)

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

Solution.

The remainder is 8.

🔗

(b)

What is the greatest common divisor of 12 and the remainder $r ?$

Solution.

$gcd (12, 8) = 4$

🔗

(c)

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} .

What is the greatest common divisor of $r$ and $r_{2} ?$

Solution.

$12 = 8 \cdot 1 + 4$ and $gcd (r, r_{2}) = gcd (8, 4) = 4$

🔗

Subsection The Euclidean Algorithm

🔗

The example in Progress Check 8.4 illustrates the main idea of the Euclidean Algorithm for finding

gcd (a, b),

which is explained in the proof of the following theorem.

🔗

Theorem 8.5.

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

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

🔗

Proof.

Let $a$ and $b$ be integers with $a \neq 0$ and $b > 0,$ and let $d = gcd (a, b) .$ By the Division Algorithm, there exist integers $q_{1}$ and $r_{1}$ such that

\begin{matrix} (67) & a = b \cdot q_{1} + r_{1},  and 0 \leq r_{1} < b . \end{matrix}

If $r_{1} = 0,$ then equation (67) implies that $b$ divides $a .$ Hence, $b = d = gcd (a, b)$ and this number satisfies Condition a and Condition b.

If $r_{1} > 0,$ then by Lemma 8.3, $gcd (a, b) = gcd (b, r_{1}) .$ We use the Division Algorithm again to obtain integers $q_{2}$ and $r_{2}$ such that

\begin{matrix} (68) & b = r_{1} \cdot q_{2} + r_{2},  and 0 \leq r_{2} < r_{1} . \end{matrix}

If $r_{2} = 0,$ then equation (68) 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 (67), 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 Condition a and Condition b.

If $r_{2} > 0,$ then by Lemma 8.3, $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 Algorithm	Inequality from Division Algorithm	New Pair
$(a, b)$	$a = b \cdot q_{1} + r_{1}$	$0 \leq r_{1} < b$	$(b, r_{1})$
$(b, r_{1})$	$b = r_{1} \cdot q_{2} + r_{2}$	$0 \leq r_{2} < r_{1}$	$(r_{1}, r_{2})$
$(r_{1}, r_{2})$	$r_{1} = r_{2} \cdot q_{3} + r_{3}$	$0 \leq r_{3} < r_{2}$	$(r_{2}, r_{3})$
$(r_{2}, r_{3})$	$r_{2} = r_{3} \cdot q_{4} + r_{4}$	$0 \leq r_{4} < r_{3}$	$(r_{3}, r_{4})$
$(r_{3}, r_{4})$	$r_{3} = r_{4} \cdot q_{5} + r_{5}$	$0 \leq 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} \dots) .$ 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 \leq 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.3 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},$ $\dots, r_{p} .$ This means that $r_{p} = gcd (a, b)$ satisfies Condition b of the theorem.

🔗

Progress Check 8.6.

🔗

(a)

Use the Euclidean Algorithm to determine $gcd (180, 126) .$ Notice that we have deleted the third column (Inequality from Division Algorithm) from the following table. It is not needed in the computations.

Original Pair	Equation from Division Algorithm	New Pair
$(180, 126)$	$180 = 126 \cdot 1 + 54$	$(126, 54)$
$(126, 54)$	$126 =$

Consequently, $gcd (180, 126) =$ .

Solution.

Original Pair	Equation from Division Algorithm	New Pair
$(180, 126)$	$180 = 126 \cdot 1 + 54$	$(126, 54)$
$(126, 54)$	$126 = 54 \cdot 2 + 18$	$(54, 18)$
$(54, 18)$	$54 = 18 \cdot 3 + 0$

Consequently, $gcd (180, 126) = 18 .$

🔗

(b)

Use the Euclidean Algorithm to determine $gcd (4208, 288) .$

Original Pair	Equation from Division Algorithm	New Pair
$(4208, 288)$	$4208 = 288 \cdot 14 + 176$	$(288,)$

Consequently, $gcd (4208, 288) =$ .

Solution.

Original Pair	Equation from Division Algorithm	New Pair
$(4208, 288)$	$4208 = 288 \cdot 14 + 176$	$(288, 176)$
$(288, 176)$	$288 = 176 \cdot 1 + 112$	$(112, 64)$
$(112, 64)$	$112 = 64 \cdot 1 + 48$	$(64, 48)$
$(64, 48)$	$64 = 48 \cdot 1 + 16$	$(48, 16)$
$(48, 16)$	$48 = 16 \cdot 3 + 0$

Consequently, $gcd (4208, 288) = 16$

🔗

Subsection Some Remarks about Theorem 8.5

🔗

Theorem 8.5 was proven with the assumptions that

a, b \in Z

with

a \neq 0

and

b > 0 .

A more general version of this theorem can be proven with

a, b \in Z

and

b \neq 0 .

This can be proven using Theorem 8.5 and the results in the following lemma.

🔗

Lemma 8.7.

Let $a, b \in Z$ with $b \neq 0 .$ Then

$gcd (0, b) = | b | .$
If $gcd (a, b) = d,$ then $gcd (a, - b) = d .$

🔗

The proofs of these results are in Exercise 4. An application of this result is given in the next example.

🔗

Example 8.8. 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 .$

🔗

Subsection Writing $gcd (a, b)$ in Terms of $a$ and $b$

🔗

We will use Example 8.8 to illustrate another use of the Euclidean Algorithm. It is possible to use the steps of the Euclidean Algorithm in reverse order to write

gcd (a, b)

in terms of

a

and

b .

We will use these steps in reverse order to find integers

m

and

n

such that

gcd (234, 42) = 234 m + 42 n .

The idea is to start with the row with the last nonzero remainder and work backward as shown in the following table:

Explanation	Result
First, use the equation in Step 3 to write 6 in terms of 24 and 18.	$6 = 24 - 18 \cdot 1$
Use the equation in Step 2 to write $18 = 42 - 24 \cdot 1 .$ Substitute this into the preceding result and simplify.	$6 = 24 - 18 \cdot 1$ $= 24 - (42 - 24 \cdot 1)$ $= 42 \cdot (- 1) + 24 \cdot 2$
We now have written 6 in terms of 42 and 24. Use the equation in Step 1 to write $24 = 234 - 42 \cdot 5 .$ Substitute this into the preceding result and simplify	$6 = 42 \cdot (- 1) + 24 \cdot 2$ $= 42 \cdot (- 1) + (234 - 42 \cdot 5) \cdot 2$ $= 234 \cdot 2 + 42 \cdot (- 11)$

🔗

Hence, we can write

gcd (234, 42) = 234 \cdot 2 + 42 \cdot (- 11) .

🔗

(Check this with a calculator.) In this case, we say that we have written

gcd (234, 42)

as a linear combination of 234 and 42. More generally, we have the following definition.

🔗

Definition.

Let $a$ and $b$ be integers. A linear combination of $a$ and $b$ is an integer of the form $a x + b y,$ where $x$ and $y$ are integers.

🔗

Progress Check 8.9. Writing the gcd as a Linear Combination.

Use the results from Progress Check 8.6 to

🔗

(a)

Write $gcd (180, 126)$ as a linear combination of 180 and 126.

Solution.

From Progress Check 8.6, $gcd (180, 126) = 18 .$

\begin{aligned} 18 & = 126 - 54 \cdot 2 \\ = 126 - (180 - 126) \cdot 2 \\ = 126 \cdot 3 + 180 \cdot (- 2) . \end{aligned}

So $gcd (180, 126) = 18,$ and $18 = 126 \cdot 3 + 180 \cdot (- 2) .$

🔗

(b)

Write $gcd (4208, 288)$ as a linear combination of 4208 and 288.

Solution.

From Progress Check 8.6, $gcd (4208, 288) = 16 .$

\begin{aligned} 16 & = 64 - 48 \\ = 64 - (112 - 64) = 64 \cdot 2 - 112 \\ = (176 - 112) \cdot 2 - 112 = 176 \cdot 2 - 112 \cdot 3 \\ = 176 \cdot 2 - (288 - 176) \cdot 3 = 176 \cdot 5 - 288 \cdot 3 \\ = (4208 - 288 \cdot 14) \cdot 5 - 288 \cdot 3 \\ = 4208 \cdot 5 + 288 \cdot (- 73) . \end{aligned}

So $gcd (4208, 288) = 16,$ and $16 = 4208 \cdot 5 + 288 \cdot (- 73) .$

🔗

The previous example and progress check illustrate the following important result in number theory, which will be used in the next section to help prove some other significant results.

🔗

Theorem 8.10.

Let $a$ and $b$ be integers, not both 0. Then $gcd (a, b)$ can be written as a linear combination of $a$ and $b .$ That is, there exist integers $u$ and $v$ such that $gcd (a, b) = a u + b v .$

🔗

We will not give a formal proof of this theorem. Hopefully, the examples and activities provide evidence for its validity. The idea is to use the steps of the Euclidean Algorithm in reverse order to write

gcd (a, b)

as a linear combination of

a

and

b .

For example, assume the completed table for the Euclidean Algorithm is

Step	Original Pair	Equation from Division Algorithm	New Pair
1	$(a, b)$	$a = b \cdot q_{1} + r_{1}$	$(b, r_{1})$
2	$(b, r_{1})$	$b = r_{1} \cdot q_{2} + r_{2}$	$(r_{1}, r_{2})$
3	$(r_{1}, r_{2})$	$r_{1} = r_{2} \cdot q_{3} + r_{3}$	$(r_{2}, r_{3})$
4	$(r_{2}, r_{3})$	$r_{2} = r_{3} \cdot q_{4} + 0$

🔗

We can use Step 3 to write

r_{3} = gcd (a, b)

as a linear combination of

r_{1}

and

r_{2} .

We can then solve the equation in Step 2 for

r_{2}

and use this to write

r_{3} = gcd (a, b)

as a linear combination of

r_{1}

and

b .

We can then use the equation in Step 1 to solve for

r_{1}

and use this to write

r_{3} = gcd (a, b)

as a linear combination of

a

and

b .

🔗

In general, if we can write

r_{p} = gcd (a, b)

as a linear combination of a pair in a given row, then we can use the equation in the preceding step to write

r_{p} = gcd (a, b)

as a linear combination of the pair in this preceding row.

🔗

The notational details of this induction argument get quite involved. Many mathematicians prefer to prove Theorem 8.10 using a property of the natural numbers called the Well-Ordering Principle. The Well-Ordering Principle for the natural numbers states that any nonempty set of natural numbers must contain a least element. It can be proven that the Well-Ordering Principle is equivalent to the Principle of Mathematical Induction.

🔗

Exercises Exercises

🔗

1.

Find each of the following greatest common divisors by listing all of the positive common divisors of each pair of integers.

🔗

(a)

$gcd (21, 28)$

Answer.

The set of positive common divisors of 21 and 28 is ${1, 7} .$ So $gcd (21, 28) = 7 .$

🔗

(b)

$gcd (- 21, 28)$

Answer.

The set of positive common divisors of $- 21$ and 28 is ${1, 7} .$ So $gcd (- 21, 28) = 7 .$

🔗

(c)

$gcd (58, 63)$

Answer.

The set of positive common divisors of 58 and 63 is ${1} .$ So $gcd (58, 63) = 1 .$

🔗

(d)

$gcd (0, 12)$

Answer.

The set of positive common divisors of 0 and 12 is ${1, 2, 3, 4, 6, 12} .$ So $gcd (0, 12) = 12 .$

🔗

(e)

$gcd (110, 215)$

🔗

(f)

$gcd (110, - 215)$

🔗

2.

Complete the following.

🔗

(a)

Let $a \in Z$ and let $k \in Z$ with $k \neq 0 .$ Prove that if $k ∣ a$ and $k ∣ (a + 1),$ then $k ∣ 1,$ and hence $k = \pm 1 .$

Hint.

Prove that $k ∣ [(a + 1) - a] .$

🔗

(b)

Let $a \in Z .$ Find the greatest common divisor of the consecutive integers $a$ and $a + 1 .$ That is, determine $gcd (a, a + 1) .$

🔗

3.

Complete the following.

🔗

(a)

Let $a \in Z$ and let $k \in Z$ with $k \neq 0 .$ Prove that if $k ∣ a$ and $k ∣ (a + 2),$ then $k ∣ 2 .$

🔗

(b)

Let $a \in Z .$ What conclusions can be made about the greatest common divisor of $a$ and $a + 2 ?$

🔗

4.

Let $a, b \in Z$ with $b \neq 0 .$ Prove each of the following:

🔗

(a)

$gcd (0, b) = | b |$

Answer.

$| b |$ is the largest natural number that divides 0 and $b .$

🔗

(b)

If $gcd (a, b) = d,$ then $gcd (a, - b) = d .$ That is, $gcd (a, - b) = gcd (a, b) .$

Answer.

The integers $b$ and $- b$ have the same divisors. Therefore, $gcd (a, - b) = gcd (a, b) .$

🔗

5.

For each of the following pairs of integers, use the Euclidean Algorithm to find $gcd (a, b)$ and to write $gcd (a, b)$ as a linear combination of $a$ and $b .$ That is, find integers $m$ and $n$ such that $d = a m + b n .$

🔗

(a)

$a = 36, b = 60$

Answer.

$gcd (36, 60) = 12,$ $12 = 36 \cdot 2 + 60 \cdot (- 1)$

🔗

(b)

$a = 901, b = 935$

Answer.

$gcd (901, 935) = 17,$ $17 = 901 \cdot 27 + 935 \cdot (- 26)$

🔗

(c)

$a = 72, b = 714$

🔗

(d)

$a = 12628, b = 21361$

🔗

(e)

$a = 901,$ $b = - 935$

Answer.

$gcd (901, - 935) = 17,$ $17 = 901 \cdot 27 + (- 935) \cdot (26)$

🔗

(f)

$a = - 36,$ $b = - 60$

🔗

6.

Complete the following.

🔗

(a)

Find integers $u$ and $v$ such that $9 u + 14 v = 1$ or explain why it is not possible to do so. Then find integers $x$ and $y$ such that $9 x + 14 y = 10$ or explain why it is not possible to do so.

Answer.

One possibility is $u = - 3$ and $v = 2 .$ In this case, $9 u + 14 v = 1 .$ We then multiply both sides of this equation by 10 to obtain

9 \cdot (- 30) + 14 \cdot 20 = 10 .

So we can use $x = - 30$ and $y = 20 .$

🔗

(b)

Find integers $x$ and $y$ such that $9 x + 15 y = 10$ or explain why it is not possible to do so.

🔗

(c)

Find integers $x$ and $y$ such that $9 x + 15 y = 3162$ or explain why it is not possible to do so.

🔗

7.

Complete the following.

🔗

(a)

Notice that $gcd (11, 17) = 1 .$ Find integers $x$ and $y$ such that $11 x + 17 y = 1 .$

Answer.

$11 \cdot (- 3) + 17 \cdot 2 = 1$

🔗

(b)

Let $m, n \in Z .$ Write the sum $\frac{m}{11} + \frac{n}{17}$ as a single fraction.

Answer.

$\frac{m}{11} + \frac{n}{17} = \frac{17 m + 11 n}{187}$

🔗

(c)

Find two rational numbers with denominators of 11 and 17, respectively , whose sum is equal to $\frac{10}{187} .$

Hint.

Write the rational numbers in the form $\frac{m}{11}$ and $\frac{n}{17},$ where $m, n \in Z .$ Then write

\frac{m}{11} + \frac{n}{17} = \frac{10}{187} .

Use Task 7.a and Task 7.b to determine $m$ and $n .$

🔗

(d)

Find two rational numbers with denominators 17 and 21, respectively, whose sum is equal to $\frac{326}{357}$ or explain why it is not possible to do so.

🔗

(e)

Find two rational numbers with denominators 9 and 15, respectively, whose sum is equal to $\frac{10}{225}$ or explain why it is not possible to do so.

🔗

Activity 47. Linear Combinations and the Greatest Common Divisor.

🔗

(a)

Determine the greatest common divisor of 20 and 12.

🔗

(b)

Let $d = gcd (20, 12) .$ Write $d$ as a linear combination of 20 and 12.

🔗

(c)

Generate at least six different linear combinations of 20 and 12. Are these linear combinations of 20 and 12 multiples of $gcd (20, 12) ?$

🔗

(d)

Determine the greatest common divisor of 21 and $- 6$ and then generate at least six different linear combinations of 21 and $- 6 .$ Are these linear combinations of 21 and $- 6$ multiples of $gcd (21, - 6) ?$

🔗

(e)

The following proposition was first introduced in Activity 30 in Section 5.2. Complete the proof of this proposition if you have not already done so.

Proposition 5.22: Let a, b, and t be integers with $t \neq 0 .$ If t divides a and t divides b, then for all integers x and y, t divides \text{(} ax + by\text{)} .

Proof. Let $a,$ $b,$ and $t$ be integers with $t \neq 0,$ and assume that $t$ divides $a$ and $t$ divides $b .$ We will prove that for all integers $x$ and $y,$ $t$ divides $(a x + b y) .$ So let $x \in Z$ and let $y \in Z .$ Since $t$ divides $a,$ there exists an integer $m$ such that $\dots .$

🔗

(f)

Now let $a$ and $b$ be integers, not both zero, and let $d = gcd (a, b) .$ Theorem 8.10 states that $d$ is a linear combination of $a$ and $b .$ In addition, let $S$ and $T$ be the following sets:

S = {a x + b y ∣ x, y \in Z} and T = {k d ∣ k \in Z} .

That is, $S$ is the set of all linear combinations of $a$ and $b,$ and $T$ is the set of all multiples of the greatest common divisor of $a$ and $b .$ Does the set $S$ equal the set $T ?$ If not, is one of these sets a subset of the other set? Justify your conclusions.

In Task 47.c and Task 47.d, we were exploring special cases for these two sets.

Section 8.1 The Greatest Common Divisor

Beginning Activity Beginning Activity 1: The Greatest Common Divisor A4US

1.

2.

Definition.

3.

4.

5.

6.

7.

8.

Beginning Activity Beginning Acivity 2: The GCD and the Division Algorithm A4US

1.

2.

Subsection The System of Integers

Subsection The Greatest Common Divisor

Lemma 8.3.

Proof.

Progress Check 8.4. Illustrations of Lemma 8.3.

(a)

(b)

(c)

Subsection The Euclidean Algorithm

Theorem 8.5.

Proof.

Progress Check 8.6.

(a)

(b)

Subsection Some Remarks about Theorem 8.5

Lemma 8.7.

Example 8.8. Using the Euclidean Algorithm.

Subsection Writing gcd(a,b) in Terms of a and b

Definition.

Progress Check 8.9. Writing the gcd as a Linear Combination.

(a)

(b)

Theorem 8.10.

Exercises Exercises

1.

(a)

(b)

(c)

(d)

(e)

(f)

2.

(a)

(b)

3.

(a)

(b)

4.

(a)

(b)

5.

(a)

(b)

(c)

(d)

(e)

(f)

6.

(a)

(b)

(c)

7.

(a)

(b)

(c)

(d)

(e)

Activity 47. Linear Combinations and the Greatest Common Divisor.

(a)

(b)

(c)

(d)

(e)

(f)

Beginning Activity Beginning Activity 1: The Greatest Common Divisor
A4 US

Beginning Activity Beginning Acivity 2: The GCD and the Division Algorithm
A4 US

Subsection Writing $gcd (a, b)$ in Terms of $a$ and $b$