Math 311W: Discrete Math Homework 4, due on Wednesday, Feb. 8 1. (i) Find the multiplication tables for Z5 and Z6 . (ii) Based on what you see in these tables, list all the invertible elements and zero-divisors in Z5 and Z6 . 2. For each of the following congruence classes [a]n , decide if it is invertible. If yes, use the Euclidean algorithm to find its inverse [a]1 n . If no, find a congruence classes [b]n such that [a]n [b]n = [0]n . a) [a]n = [15]28 . b) [a]n = [21]28 . 3. Consider the polynomial x(x 1). a) Find [a]5 ([a]5 [1]5 ) for a = 0, 1, 2, 3, 4. Give your answers in the standard form (namely, in the form of [b]5 where 0 6 b < 5). b) Use these calculations to show that there is no integer a such that (a2 a) 3 mod 5 . 4. Let n P. Consider the equation ([a]n )2 = [a]n . a) Verify that if n = k(k 1) for some integer k greater than 2, than [0]n , [1]n , and [k]n are different solutions of the equation. b) Prove that when n is a prime, the only solutions to this equation are [0]n and [1]n . 1