Results 1 to 7 of 7

Thread: equivalence relation and equivalence classes

  1. #1
    Member
    Joined
    Sep 2005
    Posts
    84

    Question 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

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,774
    Thanks
    2823
    Awards
    1
    Quote Originally Posted by rpatel View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quote Originally Posted by rpatel View Post
    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$.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2005
    Posts
    84
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by rpatel View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quote Originally Posted by rpatel View Post
    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$).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    I completely agree with hatsoff. He briefly shows the key point of this problem .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Equivalence classes for an particular relation question
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Apr 20th 2011, 02:38 PM
  2. Equivalence Relation and Classes
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 4th 2010, 08:07 AM
  3. [SOLVED] equivalence relation/classes question.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jul 28th 2009, 02:44 PM
  4. Equivalence Classes for a Cartesian Plane Relation
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Mar 5th 2009, 10:31 PM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jan 7th 2009, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum