# equivalence relation and equivalence classes

• Jan 7th 2010, 02:09 PM
rpatel
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 $\mathbb{N}$ by $xRy\Leftarrow \Rightarrow x^{2}-y^{2}$ is divisible by 7 $(x,y\in \mathbb{N})$
Prove that R is an equivalence relation on $\mathbb{N}$ and describe the equivalence classes $R_{1}$ and $R_{3}$

Any help is appreichated

thanks

(Happy)
• Jan 7th 2010, 02:25 PM
Plato
Quote:

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

Is $x^2-x^2$ divisible by 7?

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

Now what is left for you to do?
• Jan 7th 2010, 02:32 PM
hatsoff
Quote:

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

Any help is appreichated

thanks

(Happy)

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

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

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

Therefore we have the equivalence classes $[0]_7,[1]_7\cup[6]_7,[2]_7\cup[5]_7,[3]_7\cup[4]_7$ of $R$.
• Jan 7th 2010, 03:31 PM
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.

• Jan 7th 2010, 03:39 PM
Drexel28
Quote:

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.

Asssuming that hatsoff is correct with his solution, the notation $\left[n\right]_k$ usually means $\left\{n\in\mathbb{Z}:z\equiv k\text{ mod } n\right\}$. Residue classes.
• Jan 7th 2010, 04:04 PM
hatsoff
Quote:

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.

For any two integers $a,b$, an integer $n$ divides $a-b$ if and only if $a\equiv b\mod n$.
So, if $7$ divides $x-y$, then $x\equiv y\mod 7$. Similarly, if $7$ divides $x+y$, then $x\equiv -y\mod 7$. And so if $7$ divides either $x-y$ or $x+y$, then $x\equiv \pm y\mod 7$.
As for the notation issue, for some integers $k\in\mathbb{Z}^+$ and $n\in[0,k)$, we have the equivalence class $[n]_k=\{m:m\in\mathbb{Z},m\equiv n\mod k\}$ (the set of integers which, when divided by $k$, have a remainder of $n$).