7 | (m - n).4. Define the relation r on the set of integers Z
as follows: for all m and n in Z, m r n 7 | (m - n).
a) Prove that r is an equivalence relation.
Suppose that m is an integer. Now m - m = 0, and 7 | 0 since 0 = 7 · 0. Hence 7 | (m - m), so m r m. Thus the relation r is reflexive.
Suppose that m and n are integers and that m r n (so 7 | (m - n) ). Since 7 | (m - n) we know that m - n = 7 · k for some integer k. Thus n - m = 7 · (-k) and -k is also an integer. Hence 7 | (n - m) and so n r m. Thus the relation r is symmetric.
Suppose that m, n and p are integers and that m r n and n r p (so 7 | (m - n) and 7 | (n - p) ). Since 7 | (m - n) we know that m - n = 7 · k for some integer k and since 7 | (n - p) we know that n - p = 7 · h for some integer h. Hence m - p = (m - n) + (n - p) = 7 · k + 7 · h = 7 (k + h) and k + h will also be an integer. Therefore 7 | (m - p) and so m r p. Thus the relation r is transitive.
Therefore, the relation r is an equivalence relation.
b) Find the equivalence classes for r.
There are seven equivalence classes for r:
[0] = [7] = [14] = ... = { x
Z | x = 7 · k for
some integer k } = { ..., -7, 0, 7, 14, ... }
[1] = [8] = [15] = ... = { xZ | x = 7 · k + 1 for some integer k}
= { ..., -6, 1, 8, 15, ... }
[2] = [9] = [16] = ... = { xZ | x = 7 · k + 2 for some integer k}
= { ..., -5, 2, 9, 16, ... }
[3] = [10] = [17] = ... = { xZ | x = 7 · k + 3 for some integer k}
= { ..., -4, 3, 10, 17, ... }
[4] = [11] = [18] = ... = { xZ | x = 7 · k + 4 for some integer k}
= { ..., -3, 4, 11, 18, ... }
[5] = [12] = [19] = ... = { xZ | x = 7 · k + 5 for some integer k}
= { ..., -2, 5, 12, 19, ... }
[6] = [13] = [20] = ... = { xZ | x = 7 · k + 6 for some integer k}
= { ..., -1, 6, 13, 20, ... }
c) Refer to the equivalence classes from part b) to determine which of the following statements are correct? Explain your answers.
( i ) [1] = [-8]; FALSE (1 is in equivalence class [1] and -8 is in equivalence class [6].)
( ii ) [1] = [8]; TRUE (1 and 8 are both in equivalence class [1]. )
( iii ) [123] = [319]; TRUE (123 and 319 are both in equivalence class [4].)
( iv ) [304] = [-10]; FALSE (304 is in equivalence class [3] and -10 is in equivalence class [4]. )
( v ) [-34] = [-6]. TRUE (-34 and -6 are both in
equivalence class [1].)