Page 266 - Discrete Mathematics and Its Applications

4.2 Integer Representations and Algorithms 245

23. Find a div m and a mod m when 34. Show that if a ≡ b(mod m) and c ≡ d(mod m), where
a) a = 228, m = 119. a, b, c, d, and m are integers with m ≥ 2, then a − c ≡
b) a = 9009, m = 223. b − d(mod m).
c) a =−10101, m = 333. 35. Show that if n | m, where n and m are integers greater
d) a =−765432, m = 38271. than 1, and if a ≡ b(mod m), where a and b are integers,
then a ≡ b(mod n).
24. Find the integer a such that
36. Show that if a, b, c, and m are integers such that m ≥ 2,
a) a ≡ 43 (mod 23) and −22 ≤ a ≤ 0.
c> 0, and a ≡ b(mod m), then ac ≡ bc (mod mc).
b) a ≡ 17 (mod 29) and −14 ≤ a ≤ 14.
37. Find counterexamples to each of these statements about
c) a ≡−11 (mod 21) and 90 ≤ a ≤ 110.
congruences.
25. Find the integer a such that
a) If ac ≡ bc (mod m), where a, b, c, and m are integers
a) a ≡−15 (mod 27) and −26 ≤ a ≤ 0.
with m ≥ 2, then a ≡ b(mod m).
b) a ≡ 24 (mod 31) and −15 ≤ a ≤ 15. b) If a ≡ b(mod m) and c ≡ d(mod m), where
c) a ≡ 99 (mod 41) and 100 ≤ a ≤ 140. a, b, c, d, and m are integers with c and d positive
c
d
26. List five integers that are congruent to 4 modulo 12. and m ≥ 2, then a ≡ b (mod m).
2
27. List all integers between −100 and 100 that are congruent 38. Show that if n is an integer then n ≡ 0or 1 (mod 4).
to −1 modulo 25. 39. Use Exercise 38 to show that if m is a positive integer of
28. Decide whether each of these integers is congruent to the form 4k + 3 for some nonnegative integer k, then m
3 modulo 7. is not the sum of the squares of two integers.
2
a) 37 b) 66 40. Prove that if n is an odd positive integer, then n ≡
c) −17 d) −67 1 (mod 8).
29. Decide whether each of these integers is congruent to 41. Show that if a, b, k, and m are integers such that k ≥ 1,
k
k
5 modulo 17. m ≥ 2, and a ≡ b(mod m), then a ≡ b (mod m).
a) 80 b) 103 42. Show that Z m with addition modulo m, where m ≥ 2is
an integer, satisfies the closure, associative, and commu-
c) −29 d) −122
tative properties, 0 is an additive identity, and for every
30. Find each of these values.
nonzero a ∈ Z m , m − a is an inverse of a modulo m.
a) (177 mod 31 + 270 mod 31) mod 31
43. Show that Z m with multiplication modulo m, where
b) (177 mod 31 · 270 mod 31) mod 31
m ≥ 2 is an integer, satisfies the closure, associative, and
31. Find each of these values. commutativity properties, and 1 is a multiplicative iden-
a) (−133 mod 23 + 261 mod 23) mod 23 tity.
b) (457 mod 23 · 182 mod 23) mod 23 44. Show that the distributive property of multiplication over
32. Find each of these values. addition holds for Z m , where m ≥ 2 is an integer.
2
a) (19 mod 41) mod 9 45. Write out the addition and multiplication tables for Z 5
2
3
b) (32 mod 13) mod 11 (where by addition and multiplication we mean + 5
3
2
c) (7 mod 23) mod 31 and · 5 ).
2
3
d) (21 mod 15) mod 22 46. Write out the addition and multiplication tables for Z 6
33. Find each of these values. (where by addition and multiplication we mean + 6
and · 6 ).
3
2
a) (99 mod 32) mod 15
2
4
b) (3 mod 17) mod 11 47. Determine whether each of the functions f(a) = a div d
and g(a) = a mod d, where d is a fixed positive integer,
2
3
c) (19 mod 23) mod 31 from the set of integers to the set of integers, is one-to-one,
4
3
d) (89 mod 79) mod 26
and determine whether each of these functions is onto.
4.2 Integer Representations and Algorithms
Introduction
Integers can be expressed using any integer greater than one as a base, as we will show in
this section. Although we commonly use decimal (base 10), representations, binary (base 2),
octal (base 8), and hexadecimal (base 16) representations are often used, especially in computer
science. Given a base b and an integer n, we will show how to construct the base b representation
of this integer. We will also explain how to quickly covert between binary and octal and between
binary and hexadecimal notations.