## Question

###### Q2 (11 points) Let n â‚¬ N be fixed modulus such that n > 2 Consider Zn {[0], _ [n = 1]} the set of integers modulo n_ (a) Recall: for m.n â‚¬ Z (that are not both 0), we define gcd(m, n) min(S) _ where S = {kâ‚¬ N: k = mr + ny for some T.y â‚¬ Z} Using this definition for gcd, prove the following proposition: Proposition HW4 If 3[6] â‚¬ Zn such that [a] [6] = [1], then gcd(a,n) = 1 Clearly state your assumptions and carefully justify the steps of your proof using appropriate definitions and

Q2 (11 points) Let n â‚¬ N be fixed modulus such that n > 2 Consider Zn {[0], _ [n = 1]} the set of integers modulo n_ (a) Recall: for m.n â‚¬ Z (that are not both 0), we define gcd(m, n) min(S) _ where S = {kâ‚¬ N: k = mr + ny for some T.y â‚¬ Z} Using this definition for gcd, prove the following proposition: Proposition HW4 If 3[6] â‚¬ Zn such that [a] [6] = [1], then gcd(a,n) = 1 Clearly state your assumptions and carefully justify the steps of your proof using appropriate definitions and brief explanations: (b) Write the converse of the implication in Proposition HW4 c) Does the converse of Proposition HW4 hold? If so, prove it: Ifnot, provide concrete counterexample and briefly - explain. Definition_ Let [a] â‚¬ Zn- An element [b] â‚¬ Za is called multiplicative inverse for [a] if [a] @ [b] = [1]: Does [5] â‚¬ Zu have multiplicative inverse? If s0, what is *it? Briefly justify your answer: Does [3] â‚¬ Zm have multiplicative inverse? If S0, what is *it? Briefly justify your answer Which elements of Z have multiplicative inverses? For those elements (if any) find their multiplicative "inverses. Justify your answers. (IV) Which elements of Z; have multiplicative inverses? For those elements (if any) find their multiplicative *inverses. Justify your answers: #For all parts of (d) please represent multiplicative inverses using their canonical representatives [0]