retagged by
3,282 views
7 votes
7 votes
Let $S$ be the set of all integers and let $n > 1$ be a fixed integer. Define for $a,b \in  S, a R b$ iff $a-b$ is a multiple of $n$. Show that $R$ is an equivalence relation and find its equivalence classes for $n = 5$.
retagged by

2 Answers

Best answer
12 votes
12 votes

Let $ℤ$ be the set of integers, and define a relation $R$ on $ℤ$ by $aRb$ whenever the difference between $a$ and $b$ are multiples of $5.$ That is $(a,b) \in R$  if and only if $b−a=5k$ for some integer $k$. Let us show that $R$ is an equivalence relation: If $a\in ℤ$, then $a−a=0=5*0$, so $aRa$. Thus $R$ is Reflexive.

If $a,b∈ℤ$ with $aRb$, then $b−a=5k$ for some integer $k$. Thus $a−b=−(b−a)=5−5k=(−k)$. Since $−k$ is also an integer, this shows that $bRa$ and $R$ is Symmetric.

If $a,b,c ∈ ℤ$ with $aRb$ and $bRc$, then $b−a=5k$ and $c−b=5m$ for some integers $k$ and $m$. Then $c−a=(c−b)+(b−a)=5m+5k=5(m+k)$. Since $m+k$ is an integer, this shows that $aRc$ and $R$ is Transitive.
Therefore, $R$ is an Equivalence relation.

For $n=5$ the equivalence relation is called congruence modulo 5.
Equivalence classes will be 

  1. $\{a \mid a\in ℤ,  a \mod 5 = 0\}$ 
  2. $\{a \mid a\in ℤ,a \mod 5 = 1\}$ 
  3. $\{a \mid a\in ℤ,a \mod 5 = 2\}$ 
  4. $\{a \mid a\in ℤ,a \mod 5 = 3\}$ 
  5. $\{a \mid a\in ℤ,a \mod 5 = 4\}$ 
edited by
4 votes
4 votes

Let's take an example. Consider set $S=\{1,2,3,4,5,6,7\}$ and let's take n=3.

For all $a\in A, a-a=0,$ so R is reflexive.

For $a,b\in A, a-b=3c,$ for some $c\in Z\Rightarrow b-a=3(-c),$ for $-c\in Z,$ so $aRb\Rightarrow bRa$ and R is symmetric.

If $a,b,c\in A$ and $aRb,bRc,$ then $a-b=3m, b-c=3n,$ for some $m,n\in Z\Rightarrow (a-b)+(b-c)=3m+3n\Rightarrow a-c=3(m+n),$ so aRc. Consequently, R is transitive.

Equivalence classes for n=3

$[1]=[4]=[7]=\{1,4,7\}; [2]=[5]=\{2,5\}; [3]=[6]=\{3,6\}.$

$S=\{1,4,7\}\cup \{2,5\} \cup \{3,6\}$   

Similarly you can approach for n=5.

Related questions

40 votes
40 votes
4 answers
1
Kathleen asked Sep 13, 2014
7,108 views
If $G$ is a group of even order, then show that there exists an element $a≠e$, the identity in $G$, such that $a^2 = e$.
26 votes
26 votes
3 answers
2
go_editor asked Apr 24, 2016
4,563 views
Consider the set of integers $\{1,2,3,4,6,8,12,24\}$ together with the two binary operations LCM (lowest common multiple) and GCD (greatest common divisor). Which of the ...