Let S be the set of all integers and let n > 1 be a fixed integer. Define a R b for a, b in S if and only if (a - b) is a multiple of n. Show that R is an equivalence relation and find its equivalence classes for n = 5.
GATE 1992 · Discrete Mathematics · Relations · medium
Answer: R is an equivalence relation. For n = 5, the five equivalence classes are [0],[1],[2],[3],[4] where [k] = {integers with remainder k when divided by 5}.
Verify reflexivity, symmetry, transitivity: Reflexive: a - a = 0 = 0*n, so n | (a-a), hence a R a for all a. Symmetric: if n | (a-b) then a-b = k*n, so b-a = (-k)*n, meaning n | (b-a), hence b R a. Transitive: if n | (a-b) and n | (b-c) then (a-b)+(b-c) = a-c = (k1+k2)*n, so n | (a-c), hence a R c.
Find equivalence classes for n = 5: For n = 5, the equivalence class of k is [k] = {..., k-10, k-5, k, k+5, k+10, ...}. The five classes are: [0] = multiples of 5, [1] = {...,-4,1,6,11,...}, [2] = {...,-3,2,7,12,...}, [3] = {...,-2,3,8,13,...}, [4] = {...,-1,4,9,14,...}. Every integer belongs to exactly one class (its remainder when divided by 5).