$$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 8.1: The Greatest Common Divisor

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Preview Activity $$\PageIndex{1}$$: The Greatest Common Divisor

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

1. Use the roster method to list the elements of the set that contains all the natural numbers that are divisors of 48.
2. Use the roster method to list the elements of the set that contains all the natural numbers that are divisors of 84.
3. Determine the intersection of the two sets in Parts (3) and (4). This set contains all the natural numbers that are common divisors of 48 and 84.
4. What is the greatest common divisor of 48 and 84?
5. Use the method suggested in Parts (3) through (6) to determine each of the following: gcd (8, -12), gcd (0, 5), gcd (8, 27), and gcd (14, 28).
6. 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$$.

Preview Activity $$\PageIndex{2}$$: 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 Division Algorithm. (See Section 3.5, page 143.)

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

## The System of Integers

Number theory is a study of the system of integers, which consists of the set of integers, $$\mathbb{Z} = \{..., -3, -2, -1, 0, 1, 2, 3, ...\}$$ 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.

Table 8.1: Axioms for the Integers
For all integers $$a$$, $$b$$, and $$c$$;
Closure Properties for Addition and Multiplication $$a + b \in \mathbb{Z}$$ and $$ab \in \mathbb{Z}$$
Commutative Properties for Addition and Multiplication $$a + b = b + a$$, and $$ab = ba$$
Associative Properties for Addition and Multiplication $$(a + b) + c = a + (b + c)$$ and $$(ab)\ c = a\ (bc)$$
Distributive Properties of Multiplication over Addition $$a\ (b + c) = (ab + ac)$$, and $$(b + c)\ a = ba + ca$$
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 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.2: Properties of the Integers Zero Property of Multiplication If \(a \in \mathbb{Z}$$, then $$a \cdot 0 = 0 \cdot a = 0$$.
Cancellation Properties of Addition and Multiplication If $$a, b, c \in \mathbb{Z}$$, and $$a + b = a + c$$, then $$b = c$$.
If $$a, b, c \in \mathbb{Z}$$, $$a \ne 0$$ and $$ac = bc$$, 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 for Chapter 3 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 Preview Activities.

## 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 Preview Activity $$\PageIndex{1}$$.

1. If $$a, b \in \mathbb{Z}$$ and $$a$$ and $$b$$ are not both 0, and if $$d \in \mathbb{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 \le d$$.That is, any other common divisor of $$a$$ and $$b$$ is less than or equal to $$d$$.
2. 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
• $$\bullet$$ $$d$$ does not divide $$a$$ or $$d$$ does not divide $$b$$; or
• $$\bullet$$ There exists a natural number $$k$$ such that $$k\ |\ a$$ and $$k\ |\ b$$ and $$k > d$$.
3. 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 preview 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 Preview Activity $$\PageIndex{1}$$. If we look at the results in Part (7) of that preview 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

1. To find an efficient method for determining gcd($$a$$, $$b$$), where $$a$$ and $$b$$ are integers.

2. To prove that the natural number gcd($$a$$, $$b$$) is the only natural number $$d$$ that satisfies the following properties:

$$\bullet$$ $$d$$ divides $$a$$ and $$d$$ divides $$b$$; and
$$\bullet$$ 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 \le d$$ is replaced by $$k\ |\ d$$.

We will first consider the case where $$a$$ and $$b$$ are integers with $$a \ne 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 divisors 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 \le r < b$$ and gcd.b; r/ D gcd.a; b/. This idea was explored in Preview Activity $$\PageIndex{2}$$. Lemma 8.1is a conjecture that could have been formulated in Preview Activity $$\PageIndex{2}$$.

Lemma 8.1.

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 8.2: Illustrations of Lemma 8.1

We completed several examples illustrating Lemma 8.1 in Preview Activity $$\PageIndex{2}$$. 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$$?

Add texts here. Do not delete this text first.

## 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 8.3: Euclidean Algorithm

Let $$a$$ and $$b$$ be integers with $$a \ne 0$$ and $$b > 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$$.

Proof

Let $$a$$ and $$b$$ be integers with $$a \ne 0$$ and $$b > 0$$, and let $$d =$$ gcd($$a$$, $$b$$). By the Division Algorithm, 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.

Progress Check 8.4 (Using the Euclidean Algorithm)

1. 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) = .

2. 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) = .

Add texts here. Do not delete this text first.

Theorem 8.3 was proven with the assumptions that $$a, b \in \mathbb{Z}$$ with $$a \ne 0$$ and $$b > 0$$. A more general version of this theorem can be proven with $$a, b \in \mathbb{Z}$$ and $$b = 0$$. This can be proven using Theorem 8.3 and the results in the following lemma.

Lemma 8.5.

Let $$a, b \in \mathbb{Z}$$ with $$b \ne 0$$. Then

1. gcd(0, $$b$$) = |$$b$$|.
2. 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.6 (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.

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

We will use Example 8.6 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. $$\begin{array} {rcl} {6} &= & {24 - 18 \cdot 1} \end{array}$$ Use the equation in Step 2 to write $$18 = 42 - 24 \cdot 1$$. Substitute this into the preceding result and simplify. $$\begin{array} {rcl} {6} &= & {24 - 18 \cdot 1} \\ {} &= & {24 - (42 - 24 \cdot 1)} \\ {} &= & {42 \cdot (-1) + 24 \cdot 2} \end{array}$$ 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. $$\begin{array} {rcl} {6} &= & {42 \cdot (-1) + 24 \cdot 2} \\ {} &= & {42 \cdot (-1) + (234 - 42 \cdot 5) \cdot 2} \\ {} &= & {234 \cdot 2 + 42 \cdot (-11)} \end{array}$$

Hence, we can write

$$\text{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 $$ax + by$$, where $$x$$ and $$y$$ are integers.

Progress Check 8.7 (Writing the gcd as a Linear Combination)

Use the results from Progress Check 8.4 to

1. Write gcd(180, 126) as a linear combination of 180 and 126.
2. Write gcd(4208, 288) as a linear combination of 4208 and 288.

Add texts here. Do not delete this text first.

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

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 $$\text{gcd}(a, b) = au + bv$$.

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$$ $$(r_3, r_4)$$

We can use Step 3 to write $$r_3 = \text{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 = \text{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 = \text{gcd}(a, b)$$ as a linear combination of $$a$$ and $$b$$.

In general, if we can write $$r_p = \text{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 = \text{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.8 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.

Exercise 8.1

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

(a) gcd(21, 28)
(b) gcd(-21, 28)
(c) gcd(58, 63)
(d) gcd(0, 12)
(e) gcd(110, 215)
(f) gcd(110, -215)
2. (a) Let $$a \in \mathbb{Z}$$ and let $$k \in \mathbb{Z}$$ with $$k \ne 0$$. Prove that if $$k\ |\ a$$ and $$k\ |\ (a + 1)$$, then $$k\ |\ 1$$, and hence $$k = \pm1$$.
(b) Let $$a \in \mathbb{Z}$$. Find the greatest common divisor of the consecutive integers $$a$$ and $$a + 1$$. That is, determine gcd($$a$$, $$a + 1$$).
3. (a) Let $$a \in \mathbb{Z}$$ and let $$k \in \mathbb{Z}$$ with $$k \ne 0$$. Prove that if $$k\ |\ a$$ and $$k\ |\ (a + 2)$$, then $$k\ |\ 2$$.
(b) Let $$a \in \mathbb{Z}$$. Find the greatest common divisor of the common divisor $$a$$ and $$a + 2$$.
4. Let $$a, b \in \mathbb{Z}$$ with $$b \ne 0$$. Prove each of the following:

(a) gcd(0, $$b$$) = |$$b$$|
(b) If gcd($$a$$, $$b$$) = $$d$$, then gcd($$a$$, $$-b$$) = $$d$$. That is, 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 = am + bn$$.

(a) $$a = 36$$, $$b = 60$$
(b) $$a = 901$$, $$b = 935$$
(c) $$a = 72$$, $$b = 714$$
(d) $$a = 12528$$, $$b = 21361$$
(e) $$a = -36$$, $$b = -60$$
(f) $$a = 901$$, $$b = -935$$

6. (a) Find integers $$u$$ and $$v$$ such that $$9u + 14v = 1$$ or explain why it is not possible to do so. Then find integers $$x$$ and $$y$$ such that $$9x + 14y = 10$$ or explain why it is not possible to do so.
(b) Find integers $$x$$ and $$y$$ such that $$9x + 15y = 10$$ or explain why it is not possible to do so.
(c) Find integers $$x$$ and $$y$$ such that $$9x + 15y = 3162$$ or explain why it is not possible to do so.

7. (a) Notice that gcd(11, 17) = 1. Find integers $$x$$ and $$y$$ such that $$11x + 17y = 1$$.
(b) Let $$m, n \in \mathbb{Z}$$. Wrtie the sum $$\dfrac{m}{11} + \dfrac{n}{17}$$ as a single fraction.
(c) Find two rational numbers with denominators of 11 and 17, respectively, whose sum is equal to $$\dfrac{10}{187}$$. Hint: Write the rational numbers in the form $$\dfrac{m}{11} + \dfrac{n}{17}$$, where $$m, n \in \mathbb{Z}$$. Then write
$\dfrac{m}{11} + \dfrac{n}{17} = \dfrac{10}{187}.$
Use Exercises (7a) and (7b) to determine $$m$$ and $$n$$.
(d) Find two rational numbers with denominators 17 and 21, respectively, whose sum is equal to $$\dfrac{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 $$\dfrac{10}{225}$$ or explain why it is not possible to do so.

Exploration and Activities

8. Linear Combinations and the Greatest Common Divisor

(a) Determine the greatest common divisor of 20 and 12?
(b) Let $$d = \text{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 Exercise (18) on page 243 in Section 5.2. Complete the proof of this proposition if you have not already done so.

Proposition 5.16

Let $$a$$, $$b$$, and $$t$$ be integers with $$t \ne 0$$. If $$t$$ divides $$a$$ and $$t$$ divides $$b$$, then for all integers $$x$$ and $$y$$, $$t$$ divides $$ax + by$$

Proof: Let $$a$$, $$b$$ and $$t$$ be integers with $$t \ne 0$$, and assume that $$t$$ divides $$a$$ and $$t$$ divides $$b$$. We will prove that for all integers $$x$$ and $$y$$, $$t$$ divides $$(ax + by)$$.
So let $$x \in \mathbb{Z}$$ and let $$y \in \mathbb{Z}$$. Since $$t$$ divides $$a$$, there exists an integer msuch that ...
(f) Now let $$a$$ and $$b$$ be integers, not both zero and let $$d =$$ gcd($$a$$, $$b$$). Theorem 8.8 states that $$d$$ is a linear combination of $$a$$ and $$b$$. In addition, let $$S$$ and $$T$$ be the following sets:
$S = \{ax + by\ |\ x, y \in \mathbb{Z}\} \ \ \ \text{and}\ \ \ \ \ T = \{kd\ |\ k \in \mathbb{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.

Note: In Parts (c) and (d), we were exploring special cases for these two sets.