Page 328 - Discrete Mathematics and Its Applications

Supplementary Exercises 307

Review Questions

1. Find 210 div 17 and 210 mod 17. b) Express gcd(84, 119) as a linear combination of 84
2. a) Define what it means for a and b to be congruent mod- and 119.
ulo 7. 11. a) What does it mean for a to be an inverse of
b) Which pairs of the integers −11, −8, −7, −1, 0, 3, a modulo m?
and 17 are congruent modulo 7? b) How can you find an inverse of a modulo m when m
c) Show that if a and b are congruent modulo 7, then is a positive integer and gcd(a, m) = 1?
10a + 13 and −4b + 20 are also congruent modulo 7. c) Find an inverse of 7 modulo 19.
3. Show that if a ≡ b (mod m) and c ≡ d (mod m), then 12. a) How can an inverse of a modulo m be used to solve the
a + c ≡ b + d (mod m).
congruence ax ≡ b(mod m) when gcd(a, m) = 1?
4. Describe a procedure for converting decimal (base 10)
b) Solve the linear congruence 7x ≡ 13 (mod 19).
expansions of integers into hexadecimal expansions.
13. a) State the Chinese remainder theorem.
5. Convert (1101 1001 0101 1011) 2 to octal and hexadeci-
b) Find the solutions to the system x ≡ 1 (mod 4),
mal representations.
x ≡ 2 (mod 5), and x ≡ 3 (mod 7).
6. Convert (7206) 8 and (A0EB) 16 to a binary representation.
14. Suppose that 2 n−1 ≡ 1 (mod n).Is n necessarily prime?
7. State the fundamental theorem of arithmetic.
15. Use Fermat’s little theorem to evaluate 9 200 mod 19.
8. a) Describe a procedure for finding the prime factoriza-
tion of an integer. 16. Explain how the check digit is found for a 10-digit ISBN.
b) Use this procedure to find the prime factorization of 17. Encrypt the message APPLES AND ORANGES using a
80,707. shift cipher with key k = 13.
9. a) Define the greatest common divisor of two integers. 18. a) What is the difference between a public key and a pri-
b) Describe at least three different ways to find the great- vate key cryptosystem?
est common divisor of two integers. When does each b) Explain why using shift ciphers is a private key sys-
method work best? tem.
c) Find the greatest common divisor of 1,234,567 and
7,654,321. c) Explain why the RSA cryptosystem is a public key
3 5 7 9
d) Find the greatest common divisor of 2 3 5 7 11 and system.
9 7 5 3
2 3 5 7 13. 19. Explain how encryption and decryption are done in the
10. a) How can you find a linear combination (with integer RSA cryptosystem.
coefficients) of two integers that equals their greatest 20. Describe how two parties can share a secret key using the
common divisor? Diffie-Hellman key exchange protocol.

Supplementary Exercises

2
1. The odometer on a car goes to up 100,000 miles. The 7. Show that if n + 1 is a perfect square, where n is an
present owner of a car bought it when the odometer read integer, then n is even.
43,179 miles. He now wants to sell it; when you examine
8. Prove that there are no solutions in integers x and y to
the car for possible purchase, you notice that the odome- 2 2
the equation x − 5y = 2. [Hint: Consider this equation
ter reads 89,697 miles. What can you conclude about how
modulo 5.]
many miles he drove the car, assuming that the odometer
always worked correctly?
9. Develop a test for divisibility of a positive integer n by 8
2. a) Explain why n div 7 equals the number of complete based on the binary expansion of n.
weeks in n days.
10. Develop a test for divisibility of a positive integer n by 3
b) Explain why n div 24 equals the number of complete based on the binary expansion of n.
days in n hours.
3. Find four numbers congruent to 5 modulo 17. 11. Devise an algorithm for guessing a number between 1
n
and 2 − 1 by successively guessing each bit in its binary
4. Show that if a and d are positive integers, then there are
expansion.
integers q and r such that a = dq + r where −d/2 <r ≤
d/2. 12. Determine the complexity, in terms of the number of
∗ 5. Show that if ac ≡ bc (mod m), where a, b, c, and guesses, needed to determine a number between 1 and
n
m are integers with m> 2, and d = gcd(m, c), then 2 − 1 by successively guessing the bits in its binary ex-
a ≡ b(mod m/d). pansion.
6. Show that the sum of the squares of two odd integers 13. Show that an integer is divisible by 9 if and only if the
cannot be the square of an integer. sum of its decimal digits is divisible by 9.