d | (m - n) for some integer d.6. Define the relation d on the set of integers Z
as follows: for all m and n in Z, m d n d | (m - n) for some integer d.
a) Prove that d is an equivalence relation.
Suppose that m is an integer. Now m - m = 0, and d | 0 since 0 = d � 0. Hence d | (m - m), so m d m. Thus the relation d is reflexive.
Suppose that m and n are integers and that m d n (so d | (m - n) ). Since d | (m - n) we know that m - n = d � k for some integer k. Thus n - m = d � (-k) and -k is also an integer. Hence d | (n - m) and so n d m. Thus the relation d is symmetric.
Suppose that m, n and p are integers and that m d n and n d p (so d | (m - n) and d | (n - p) ). Since d | (m - n) we know that m - n = d � k for some integer k and since d | (n - p) we know that n - p = d � h for some integer h. Hence m - p = (m - n) + (n - p) = d � k + d � h = d (k + h) and k + h will also be an integer. Therefore d | (m - p) and so m d p. Thus the relation d is transitive.
Therefore, the relation d is an equivalence relation.
b) Find the equivalence classes for d.
There are d equivalence classes for d:
[0] = [d] = [2d] = ... = { x
Z | x = d � k for
some integer k } = { ..., -d, 0, d, 2d, ... }
[1] = [d + 1] = [2d + 1] = ... = { xZ | x = d � k + 1 for some integer k}
= { ..., -d + 1, 1, d + 1, 2d + 1, ... }
[2] = [d + 2] = [2d + 2] = ... = { xZ | x = d � k + 2 for some integer k}
= { ..., -d + 2, 2, d + 2, 2d + 2, ... }
[3] = [d + 3] = [2d + 3] = ... = { xZ | x = d � k + 3 for some integer k}
= { ..., -d + 3, 3, d + 3, 2d + 3, ... }
:
:
[d-2] = [d + (d-2)] = [2d + (d-2)] = ... = { xZ | x = d � k + (d-2) for some
integer k} = { ..., -d + (d-2), d-2, d + (d-2), 2d + (d-2), ... }
[d-1] = [d + (d-1)] = [2d + (d-1)] = ... = { xZ | x = d � k + (d-1) for some
integer k} = { ..., -d + (d-1), d-1, d + (d-1), 2d + (d-1), ... }