§1.2 Exercises

Exercises 1.2.A

Exercise 1.2.1

Find the greatest common divisors. You should be able to do parts (a)–(c) by hand, but technology is OK for the rest.

  • (a) \((56, 72)\)
  • (b) \((24, 138)\)
  • (c) \((112, 57)\)
  • (d) \((143, 231)\)
  • (e) \((306, 657)\)
  • (f) \((272, 1479)\)
  • (g) \((4144, 7696)\)
  • (h) \((12378, 3054)\)

Exercise 1.2.2

Prove that \(b \mid a\) if and only if \((-b) \mid a\).

Exercise 1.2.3

If \(a \mid b\) and \(b \mid c\), prove that \(a \mid c\).

Exercise 1.2.4

(a) If \(a \mid b\) and \(a \mid c\), prove that \(a \mid (b + c)\).

(b) If \(a \mid b\) and \(a \mid c\), prove that \(a \mid (br + ct)\) for any \(r, t \in \mathbb{Z}\).

Exercise 1.2.5

If \(a\) and \(b\) are nonzero integers such that \(a \mid b\) and \(b \mid a\), prove that \(a = \pm b\).

Exercise 1.2.6

If \(a \mid b\) and \(c \mid d\), prove that \(ac \mid bd\).

Exercise 1.2.7

If \(a < 0\), find \((a, 0)\).

Exercise 1.2.8

Prove that \((n, n + 1) = 1\) for every integer \(n\).

Exercise 1.2.9

If \(a \mid c\) and \(b \mid c\), must \(ab \mid c\)? Justify your answer.

Exercise 1.2.10

If \((a, 0) = 1\), what can \(a\) possibly be?

Exercise 1.2.11

If \(n \in \mathbb{Z}\), what are the possible values of:

  • (a) \((n, n + 2)\)
  • (b) \((n, n + 6)\)

Exercise 1.2.12

Suppose that \((a, b) = 1\) and \((a, c) = 1\). Are any of the following statements false? Justify your answers.

  • (a) \((ab, a) = 1\)
  • (b) \((b, c) = 1\)
  • (c) \((ab, c) = 1\)

Exercise 1.2.13

Suppose that \(a\), \(b\), \(q\), and \(r\) are integers such that \(a = bq + r\). Prove each of the following statements.

  • (a) Every common divisor \(c\) of \(a\) and \(b\) is also a common divisor of \(b\) and \(r\).
  • (b) Every common divisor of \(b\) and \(r\) is also a common divisor of \(a\) and \(b\).
  • (c) \((a, b) = (b, r)\).

Hint: For some integers \(s\) and \(t\), we have \(a = cs\) and \(b = ct\). Substitute these results into \(a = bq + r\), and show that \(c \mid r\).

Exercise 1.2.14

Find the smallest positive integer in the given set.

  • (a) \(\{6u + 15v \mid u, v \in \mathbb{Z}\}\)
  • (b) \(\{12r + 17s \mid r, s \in \mathbb{Z}\}\)

Hint: Theorem 1.2

Exercise 1.2.15

The Euclidean Algorithm is an efficient way to find \((a, b)\) for any positive integers \(a\) and \(b\). It only requires you to apply the Division Algorithm several times until you reach the gcd, as illustrated here for \((524, 148)\).

(a) Verify that the following statements are correct.

\[ \begin{aligned} 524 &= 148 \cdot 3 + 80 & 0 &< 80 < 148 \\ 148 &=80 \cdot 1 + 68 & 0 &< 68 < 80 \\ 80 &=68 \cdot 1 + 12 & 0 &< 12 < 68 \\ 68 &=12 \cdot 5 + 8 & 0 &< 8 < 12 \\ 12 &=8 \cdot 1 + 4 & 0 &< 4 < 8 \\ 8 &=4 \cdot 2 + 0 \\ \end{aligned} \]

As shown in part (b), the last nonzero remainder, namely 4, is the gcd \((a, b)\).

(b) Use part (a) and Exercises 13 and Example 4 to prove that

\[ (524, 148) = (148, 80) = (80, 68) = (68, 12) = (12, 8) = (8, 4) = (4, 0) = 4. \]

Use the Euclidean Algorithm to find

  • (c) \((1003, 456)\)
  • (d) \((322, 148)\)
  • (e) \((5858, 1436)\)

The equations in part (a) can be used to express the gcd 4 as a linear combination of 524 and 148 as follows. First, rearrange the first 5 equations in part (a), as shown below.

\[ \begin{aligned} 80 &= 524 - 148 \cdot 3 &\text{(1)} \\ 68 &= 148 - 80 &\text{(2)} \\ 12 &= 80 - 68 \cdot 1 &\text{(3)} \\ 8 &= 68 - 12 \cdot 5 &\text{(4)} \\ 4 &= 12 - 8 &\text{(5)} \end{aligned} \]

(f) Equation (1) expresses 80 as a linear combination of 524 and 148. Use this fact and Equation (2) to write 68 as a linear combination of 524 and 148.

(g) Use Equation (1), part (f), and Equation (3) to write 12 as a linear combination of 524 and 148.

(h) Use parts (f) and (g) to write 8 as a linear combination of 524 and 148.

(i) Use parts (g) and (h) to write the gcd 4 as a linear combination of 524 and 148, as desired.

(j) Use the method described in parts (f)–(i) to express the gcd in part (c) as a linear combination of 1003 and 456.

Exercises 1.2.B

Exercise 1.2.16

If \((a, b) = d\), prove that \(\left(\frac{a}{d}, \frac{b}{d}\right) = 1\).

Hint: \(a = dr\) and \(b = ds\) for some integers \(r\) and \(s\). So \(\frac{a}{d} = r\) and \(\frac{b}{d} = s\) and you must prove that \((r, s) = 1\). Apply Theorem 1.2 to \((a, b)\) and divide the resulting equation by \(d\).

Exercise 1.2.17

Suppose \((a, b) = 1\). If \(a \mid c\) and \(b \mid c\), prove that \(ab \mid c\).

Hint: \(c = bt\) (Why?), so \(a \mid bt\). Use Theorem 1.4.

Exercise 1.2.18

If \(c > 0\), prove that \((ca, cb) = c(a, b)\).

Hint: Let \((a, b) = d\) and \((ca, cb) = k\). Show that \(cd \mid k\) and \(k \mid cd\). See Exercise 5.

Exercise 1.2.19

If \(a \mid (b + c)\) and \((b, c) = 1\), prove that \((a, b) = 1 = (a, c)\).

Exercise 1.2.20

Prove that \((a, b) = (a, b + at)\) for every \(t \in \mathbb{Z}\).

Exercise 1.2.21

Prove that \((a, (b, c)) = ((a, b), c)\).

Exercise 1.2.22

If \((a, c) = 1\) and \((b, c) = 1\), prove that \((ab, c) = 1\).

Exercise 1.2.23

Use induction to show that if \((a, b) = 1\), then \((a, b^n) = 1\) for all \(n \geq 1\).

Induction is discussed in Appendix C.

Exercise 1.2.24

Let \(a\), \(b\), \(c \in \mathbb{Z}\). Prove that the equation \(ax + by = c\) has integer solutions if and only if \((a, b) \mid c\).

Exercise 1.2.25

(a) If \(a\), \(b\), \(u\), \(v \in \mathbb{Z}\) are such that \(au + bv = 1\), prove that \((a, b) = 1\).

(b) Show by example that if \(au + bv = d > 1\), then \((a, b)\) may not be \(d\).

Exercise 1.2.26

If \(a \mid c\) and \(b \mid c\), prove that \((a, b) \mid c\).

Exercise 1.2.27

If \(a \mid b\) and \((a, c) = d\), prove that \((a, b) = d\).

Exercise 1.2.28

Prove that a positive integer is divisible by 3 if and only if the sum of its digits is divisible by 3.

Hint: \(10^3 = 999 + 1\) and similarly for other powers of 10.

Exercise 1.2.29

Prove that a positive integer is divisible by 9 if and only if the sum of its digits is divisible by 9.

Hint: See Exercise 28.

Exercise 1.2.30

If \(a_1, a_2, \dots, a_n\) are integers, not all zero, then their greatest common divisor (gcd) is the largest integer \(d\) such that \(d \mid a_i\) for every \(i\). Prove that there exist integers \(u_i\) such that

\(d = a_1u_1 + a_2u_2 + \dots + a_nu_n\).

Hint: Adapt the proof of Theorem 1.2.

Exercise 1.2.31

The least common multiple (lcm) of nonzero integers \(a_1, a_2, \dots, a_k\) is the smallest positive integer \(m\) such that \(a_i \mid m\) for \(i = 1, 2, \dots, k\), and is denoted \([a_1, a_2, \dots, a_k]\).

(a) Find each of the following: \([6, 10]\), \([4, 5, 6]\), \([20, 42]\), and \([2, 3, 14, 36, 42]\).

(b) If \(t\) is an integer such that \(a_i \mid t\) for \(i = 1, 2, \dots, k\), prove that \([a_1, a_2, \dots, a_k] \mid t\).

Hint: Denote \([a_1, a_2, \dots, a_k]\) by \(m\). By the Division Algorithm, \(t = mq + r\), with \(0 \leq r < m\). Show that \(a_i \mid r\) for \(i=1, 2, \dots, k\). Since \(m\) is the smallest positive integer with this property, what can you conclude about \(r\)?

Exercise 1.2.32

Let \(a\) and \(b\) be integers, not both 0, and let \(t\) be a positive integer. Prove that \(t\) is the least common multiple of \(a\) and \(b\) if and only if \(t\) satisfies these conditions:

  1. (i) \(a \mid t\) and \(b \mid t\);
  2. (ii) If \(c \mid a\) and \(c \mid b\), then \(t \mid c\).

Exercises 1.2.C

Exercise 1.2.33

If \(a > 0\) and \(b > 0\), prove that \([a, b] = \frac{ab}{(a, b)}\).

Note: The \([a, b]\) is defined in Exercise 31.

Exercise 1.2.34

Prove that:

  • (a) \((a, b) \mid (a + b, a - b)\);
  • (b) if \(a\) is odd and \(b\) is even, then \((a, b) = (a + b, a - b)\);
  • (c) if \(a\) and \(b\) are odd, then \(2(a, b) = (a + b, a - b)\).