444
Relations, Functions, and Matrices
34. A taxpayer wants his tax refund to be deposited directly to his bank. He enters the bank’s routing number,
including the check digit, as
025107036
Is this routing number correct?
35. a. Write an algorithm to decompose a four-digit integer into the ones, tens, hundreds, and thousands
digits.
b. Apply this algorithm to decompose the integer 7426.
36. The following quilt image is based on addition modulo n for what value of n?
Exercises 37–41 involve a proof of step 7 of the RSA method.
37. Prove that if x ≡ y (mod n) and c is a constant integer, then xc ≡ yc (mod n).
38. This exercise explores the converse of Exercise 37, which is the issue of cancellation under congruence modulo n. In other words, if xc ≡ yc (mod n) for some constant integer c, is it then true that
x ≡ y (mod n)? Not always, as it turns out.
a. Prove that if gcd(c,n) = 1, then xc ≡ yc (mod n) implies x ≡ y (mod n).
b. Prove that xc ≡ yc (mod n) implies x ≡ y (mod n) only if gcd (c, n) = 1. To do this, it is easier to
prove the contrapositive:
If gcd (c, n) ∙ 1, then there exist integer values x and y for which xc ≡ yc (mod n) but x [ y mod n.
(Hint: Suppose c = m 1 k and n = m 2 k with k > 1. Consider x = m 2 k and y = m 2 .)
c. Find values for x, y, c, and n where xc ≡ yc (mod n) but x [ y (mod n).
39. If p is a prime number and a is a positive integer not divisible by p, then
a
p−1
≡ 1(mod p)
Relations, Functions, and Matrices
34. A taxpayer wants his tax refund to be deposited directly to his bank. He enters the bank’s routing number,
including the check digit, as
025107036
Is this routing number correct?
35. a. Write an algorithm to decompose a four-digit integer into the ones, tens, hundreds, and thousands
digits.
b. Apply this algorithm to decompose the integer 7426.
36. The following quilt image is based on addition modulo n for what value of n?
Exercises 37–41 involve a proof of step 7 of the RSA method.
37. Prove that if x ≡ y (mod n) and c is a constant integer, then xc ≡ yc (mod n).
38. This exercise explores the converse of Exercise 37, which is the issue of cancellation under congruence modulo n. In other words, if xc ≡ yc (mod n) for some constant integer c, is it then true that
x ≡ y (mod n)? Not always, as it turns out.
a. Prove that if gcd(c,n) = 1, then xc ≡ yc (mod n) implies x ≡ y (mod n).
b. Prove that xc ≡ yc (mod n) implies x ≡ y (mod n) only if gcd (c, n) = 1. To do this, it is easier to
prove the contrapositive:
If gcd (c, n) ∙ 1, then there exist integer values x and y for which xc ≡ yc (mod n) but x [ y mod n.
(Hint: Suppose c = m 1 k and n = m 2 k with k > 1. Consider x = m 2 k and y = m 2 .)
c. Find values for x, y, c, and n where xc ≡ yc (mod n) but x [ y (mod n).
39. If p is a prime number and a is a positive integer not divisible by p, then
a
p−1
≡ 1(mod p)