# Thread: equivalence relation and equivalence classes

1. ## equivalence relation and equivalence classes

Hi i need help with this following question. I am not sure on how to approach it.

Define the relation R on $\displaystyle \mathbb{N}$ by $\displaystyle xRy\Leftarrow \Rightarrow x^{2}-y^{2}$ is divisible by 7 $\displaystyle (x,y\in \mathbb{N})$
Prove that R is an equivalence relation on $\displaystyle \mathbb{N}$ and describe the equivalence classes $\displaystyle R_{1}$ and $\displaystyle R_{3}$

Any help is appreichated

thanks

2. Originally Posted by rpatel
Define the relation R on $\displaystyle \mathbb{N}$ by $\displaystyle xRy\Leftarrow \Rightarrow x^{2}-y^{2}$ is divisible by 7 $\displaystyle (x,y\in \mathbb{N})$
Prove that R is an equivalence relation on $\displaystyle \mathbb{N}$ and describe the equivalence classes $\displaystyle R_{1}$ and $\displaystyle R_{3}$
Is $\displaystyle x^2-x^2$ divisible by 7?

If $\displaystyle x^2-y^2$ is divisible by 7 is $\displaystyle y^2-x^2?$

Now what is left for you to do?

3. Originally Posted by rpatel
Hi i need help with this following question. I am not sure on how to approach it.

Define the relation R on $\displaystyle \mathbb{N}$ by $\displaystyle xRy\Leftarrow \Rightarrow x^{2}-y^{2}$ is divisible by 7 $\displaystyle (x,y\in \mathbb{N})$
Prove that R is an equivalence relation on $\displaystyle \mathbb{N}$ and describe the equivalence classes $\displaystyle R_{1}$ and $\displaystyle R_{3}$

Any help is appreichated

thanks

Since 7 is prime, then if $\displaystyle 7\big|(x^2-y^2)$ we have

$\displaystyle 7\big|(x-y)$ or $\displaystyle 7\big|(x+y)$, such that

$\displaystyle xRy\Leftrightarrow x\equiv\pm y\mod 7$.

Therefore we have the equivalence classes $\displaystyle [0]_7,[1]_7\cup[6]_7,[2]_7\cup[5]_7,[3]_7\cup[4]_7$ of $\displaystyle R$.

4. how did you calculate the equivalence classes because i know that some being mod 7 means it divisble by some multiple of 7 and remainder is written in the front of the mod7. hence 34=6mod7 since 34-(7x4)=6.

but i don't understand how you've done it in terms of x and y. and also could you please explain the sqaure bracket notation for the equivalence classes. I have seen this notation before but i don't understand what the number inside the brackets and the lower case power to it means.

thanks for your help

5. Originally Posted by rpatel
how did you calculate the equivalence classes because i know that some being mod 7 means it divisble by some multiple of 7 and remainder is written in the front of the mod7. hence 34=6mod7 since 34-(7x4)=6.

but i don't understand how you've done it in terms of x and y. and also could you please explain the sqaure bracket notation for the equivalence classes. I have seen this notation before but i don't understand what the number inside the brackets and the lower case power to it means.

thanks for your help
Asssuming that hatsoff is correct with his solution, the notation $\displaystyle \left[n\right]_k$ usually means $\displaystyle \left\{n\in\mathbb{Z}:z\equiv k\text{ mod } n\right\}$. Residue classes.

6. Originally Posted by rpatel
how did you calculate the equivalence classes because i know that some being mod 7 means it divisble by some multiple of 7 and remainder is written in the front of the mod7. hence 34=6mod7 since 34-(7x4)=6.

but i don't understand how you've done it in terms of x and y. and also could you please explain the sqaure bracket notation for the equivalence classes. I have seen this notation before but i don't understand what the number inside the brackets and the lower case power to it means.

thanks for your help
Sure thing. You may wish to memorize this extremely useful theorem:

For any two integers $\displaystyle a,b$, an integer $\displaystyle n$ divides $\displaystyle a-b$ if and only if $\displaystyle a\equiv b\mod n$.

So, if $\displaystyle 7$ divides $\displaystyle x-y$, then $\displaystyle x\equiv y\mod 7$. Similarly, if $\displaystyle 7$ divides $\displaystyle x+y$, then $\displaystyle x\equiv -y\mod 7$. And so if $\displaystyle 7$ divides either $\displaystyle x-y$ or $\displaystyle x+y$, then $\displaystyle x\equiv \pm y\mod 7$.

As for the notation issue, for some integers $\displaystyle k\in\mathbb{Z}^+$ and $\displaystyle n\in[0,k)$, we have the equivalence class $\displaystyle [n]_k=\{m:m\in\mathbb{Z},m\equiv n\mod k\}$ (the set of integers which, when divided by $\displaystyle k$, have a remainder of $\displaystyle n$).

7. I completely agree with hatsoff. He briefly shows the key point of this problem .