Formal MethodsKey to Homework Assignment 12, Part 2Monday, April 30, 2007Note: You should assume that n is a positive integer ≥ 2.Recall the following two definitions from class. A nonzero element [a] ∈ Z/n is a zero divisorif there exists a nonzero element [b] ∈ Z/n such that [a][b] = [0]. A nonzero element [c] ∈ Z/n is aunit if there exists a nonzero element [d] ∈ Z/n such that [b][d] = [1].1. In class we proved that if [a] is a nonzero element of Z/n, then [a] cannot both be a zerodivisor and a unit. From this it follows that if [a] is a zero divisor then [a] is not a unit, andif [a] is a unit, it’s not a zero divisor.Consider the setsD = {[a] ∈ Z/n : [a] is a zero divisor }, and U = {[c] ∈ Z/n : [c] is a unit }.From our discussion in class, it follows that D ∩ U = ∅.(a) For n = 2, 3, 4, 5, 6, find D and U.From the multiplication tables we looked at in class, we can see thati. In Z/2, D = ∅, and U = {1}.ii. In Z/3, D = ∅, and U = {1, 2}.iii. In Z/4, D = {2}, and U = {1, 3}.iv. In Z/5, D = ∅, and U = {1, 2, 3, 4}.v. In Z/6, D = {2, 3, 4}, and U = {1, 5}.(b) In general, is it true that the nonzero elements of Z/n belong to D ∪ U? (You don’t needto prove anything here.)Yes, Z/n−{0} = D ∪U. To see this, suppose that a is an integer such that 0 < a ≤ n−1.Consider the setA = {[0][a], [1][a], [2][a], . . . , [n − 1][a]}.Since A ⊆ Z/n, |A| ≤ n. If |A| = n, then [1] ∈ A. So for some [b] ∈ Z/n, [a][b] = [1], and[a] ∈ U. So suppose that |A| < n. Then for some integer c, 0 ≤ c ≤ n−1, [c] /∈ A. So thereexist two integers d and e such that 0 ≤ d < e ≤ n − 1, and [d][a] = [da] = [ea] = [e][a].By definition, then, there exists an integer k such that ea − da = (e − d)a = kn. But0 < e − d ≤ n − 1. So [e − d] is a nonzero element of Z/n such that [e − d][a] = [0]. Soe − d is a zero divisor, and a is also a zero divisor. That is, [a] ∈ D.2. In class we conjectured that all of the nonzero elements of Z/n are units if n is prime. Whatare the units in Z/7? What are the units in Z/11?1(a) The units of Z/7 are {1, 2, 3, 4, 5, 6}. To see this, observe that in Z/7,[1][1] = [1], [2][4] = [1], [3][5] = [1], and [6][6] = [1].(b) The units of Z/11 are {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. To see this, observe that in Z/11,[1] = [1][1] = [2][6] = [3][4] = [5][9] = [7][8] = [10][10].3. In class we conjectured that if n is composite, then Z/n contains elements that are not units.What are the nonunits in Z/8 and Z/9?(a) In Z/8, [1], [3], [5], [7] are units because[1] = [1][1] = [3][3] = [5][5] = [7][7].The remaining nonzero elements are nonunits: [2], [4], [6]. By the result that zero divisorscan’t be units, we can see that all of these are nonunits, because all are zero divisors:[0] = [2][4] = [6][4].Note that [0] is always a nonunit.(b) In Z/9, the units are [1], [2], [4], [5], [7], [8] because[1] = [1][1] = [2][5] = [4][7] = [8][8].The remaining nonzero elements are zero divisors because[0] = [3][3] = [6][6].So the nonunits are [0], [3], and