Math 311W: Discrete Math Homework 5, due on Friday, Feb. 17 Note: Whenever applicable, please give your final answers using the standard representatives, i.e., in the form [a]n where 0 6 a < n. 1. Solve the simultaneous linear congruence x 6 mod 9 3x 2 mod 4 2x 4 mod 10 . 2. Recall that (n) is the number of invertible elements in Zn . a) Use Theorem 1.6.5 and Theorem 1.6.6 to find (28). b) Does 3 have finite multiplicative order modulo 28? Why? Find the order of [3]28 . c) Use (b) to find [3311 ]28 . 3. Follow the steps below to encrypt a message with a public key consisting of the base 221 and the exponent 5. You may use a calculator to help you. a) Use the top secretthe prime factorization 221 = 13 17to find (221). b) Use the Euclidean algorithm to find [5]1 (221) . c) Pick an integer from 0 to 10 to be the number of points you want to get for this homework. Let m be that number plus 1 and write it down. Example: if you want to get 10 points, write down \"m = 11\". d) Use the RSA encryption system to encode m with the public key (namely, the base 221 and the exponent 5). e) Briefly explain how the receiver can decode this message. 1