Page 265 - Discrete Mathematics and Its Applications

244 4 / Number Theory and Cryptography

Remark: Because Z m with the operations of addition and multiplication modulo m satisfies
the properties listed, Z m with modular addition is said to be a commutative group and Z m
with both of these operations is said to be a commutative ring. Note that the set of integers
with ordinary addition and multiplication also forms a commutative ring. Groups and rings are
studied in courses that cover abstract algebra.

Remark: In Exercise 30, and in later sections, we will use the notations + and · for + m and · m
without the subscript m on the symbol for the operator whenever we work with Z m .

Exercises

1. Does 17 divide each of these numbers? 13. Suppose that a and b are integers, a ≡ 4 (mod 13), and
a) 68 b) 84 c) 357 d) 1001 b ≡ 9 (mod 13). Find the integer c with 0 ≤ c ≤ 12 such
that
2. Prove that if a is an integer other than 0, then
a) 1 divides a. b) a divides 0. a) c ≡ 9a(mod 13).
b) c ≡ 11b(mod 13).
3. Prove that part (ii) of Theorem 1 is true.
c) c ≡ a + b(mod 13).
4. Prove that part (iii) of Theorem 1 is true. d) c ≡ 2a + 3b(mod 13).
2
2
5. Show that if a | b and b | a, where a and b are integers, e) c ≡ a + b (mod 13).
3
3
then a = b or a =−b. f) c ≡ a − b (mod 13).
6. Show that if a, b, c, and d are integers, where a = 0, such 14. Suppose that a and b are integers, a ≡ 11 (mod 19), and
that a | c and b | d, then ab | cd. b ≡ 3 (mod 19). Find the integer c with 0 ≤ c ≤ 18 such
7. Show that if a, b, and c are integers, where a = 0 and that
c = 0, such that ac | bc, then a | b. a) c ≡ 13a(mod 19).
b) c ≡ 8b(mod 19).
8. Prove or disprove that if a | bc, where a, b, and c are pos-
itive integers and a = 0, then a | b or a | c. c) c ≡ a − b(mod 19).
d) c ≡ 7a + 3b(mod 19).
9. What are the quotient and remainder when 2 2
e) c ≡ 2a + 3b (mod 19).
a) 19 is divided by 7? f) c ≡ a + 4b (mod 19).
3
3
b) −111 is divided by 11?
15. Let m be a positive integer. Show that a ≡ b(mod m) if
c) 789 is divided by 23? a mod m = b mod m.
d) 1001 is divided by 13?
16. Let m be a positive integer. Show that a mod m =
e) 0 is divided by 19?
b mod m if a ≡ b(mod m).
f) 3 is divided by 5?
17. Show that if n and k are positive integers, then n/k =
g) −1 is divided by 3?
(n − 1)/k + 1.
h) 4 is divided by 1?
18. Show that if a is an integer and d is an inte-
10. What are the quotient and remainder when
ger greater than 1, then the quotient and remain-
a) 44 is divided by 8? der obtained when a is divided by d are a/d and
b) 777 is divided by 21? a − d a/d , respectively.
c) −123 is divided by 19? 19. Find a formula for the integer with smallest absolute value
d) −1 is divided by 23? that is congruent to an integer a modulo m, where m is a
e) −2002 is divided by 87? positive integer.
f) 0 is divided by 17? 20. Evaluate these quantities.
g) 1,234,567 is divided by 1001?
a) −17 mod 2 b) 144 mod 7
h) −100 is divided by 101? c) −101 mod 13 d) 199 mod 19
11. What time does a 12-hour clock read 21. Evaluate these quantities.
a) 80 hours after it reads 11:00? a) 13 mod 3 b) −97 mod 11
b) 40 hours before it reads 12:00? c) 155 mod 19 d) −221 mod 23
c) 100 hours after it reads 6:00? 22. Find a div m and a mod m when
12. What time does a 24-hour clock read a) a =−111, m = 99.
a) 100 hours after it reads 2:00? b) a =−9999, m = 101.
b) 45 hours before it reads 12:00? c) a = 10299, m = 999.
c) 168 hours after it reads 19:00? d) a = 123456, m = 1001.