Question

1. Write down the addition and multiplication table for Z/5Z. All classes should be written in terms of their canonical representative (unique representative between 0 and 4).

2. Suppose a ≡ a' mod n and b ≡ b' mod n.

(a) Show that a + b ≡ a' + b' mod n.

(b) Show that a · b ≡ a' · b' mod n. (An important consequence of this exercise is that addition and multiplication define maps Z/nZ × Z/nZ → Z/nZ. This is not obvious from the definition of addition and multiplication, because the definitions require you to choose representatives for equivalence classes. Different choices of representatives could conceivably result in different outcomes for the sum or product of the same pair of elements. A map, however, is not allowed to send the same pair of elements to multiple distinct elements. For example, in Z/123Z, we have [10] + [5] = [10 + 5] = [15] by definition. However, [10] = [625] and [5] = [866]. Applying the definition of sum again yields [625] + [866] = [1491]. If addition does define a map, then it should be the case that [15]=[1491], otherwise the pair ([10],[5]) would be mapped to two distinct values. A simple check shows that this is indeed the case here, and this exercise shows that this will be true in general.)

3. We extend the notion of divisibility to Z/nZ in the obvious way: [a]|[b] if [b] = [k] · [a] for some k ∈ Z.

(a) Prove that [a]|[b] if and only if gcd(a, n)|b. (Hint: use problem 1: Let a, b, c ∈ Z. Prove that c = ma + nb for some m, n ∈ Z if and only if gcd(a, b)|c.)

(b) Conclude from part (a) that [a] has a multiplicative inverse if and only if gcd(a, n) = 1.

Answer 1