# 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 $\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

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

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?
• 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 $\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

(Happy)

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$.
• 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.

thanks for your help
• 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.

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.
• 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.

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$).
• Jan 7th 2010, 06:36 PM
Shanks
I completely agree with hatsoff. He briefly shows the key point of this problem .