Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding the no of equivalent classes

  1. Oct 21, 2010 #1
    1. The problem statement, all variables and given/known dataplease consider the relation over the set of integers Z , given by m=n mod (p) where p is a positive integer . Prove that it is an equivalent relation.
    find the elements in the equivalent class of m.
    find the no of such equivalent classes.

    2. Relevant equations

    3.equivalent relation-proved by showing reflexivity, symmetry and transitivity.
    the equivalent class of m consists of elements of the type
    m +k p where k = 0,+/-1,+/-2......
    but i am not able to think how to find the no of such classes. any help will be highly appreciated.
  2. jcsd
  3. Oct 21, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper

    hi commutator! :smile:

    (have a ± :wink:)
    that's right! :smile:

    ok, when you're stuck it's often useful to try an easy example …

    if p = 10, what are the equivalence classes? :wink:
  4. Oct 21, 2010 #3
    thanks . that was really encouraging.

    for p=10, i got something like [-1]=(.....,-11,-21-1,9,19,29......)
    interestingly , [11] is coming same as [1]. [-1] is coming the same as [9].so i think there are 10 distinct classes, which are repeating over and over. then the answer has got to be 10. ie. p. but how do i sketch a formal proof ? by induction?
  5. Oct 21, 2010 #4


    User Avatar
    Science Advisor
    Homework Helper

    hi commutator! :smile:
    that's right, there's exactly p classes

    the formal proof isn't the problem …

    the problem is the formal definition

    once you have that, the proof is obvious

    eg your definition {...-29,-19....1,11,21,31...} is only a list, so that's not helpful, but your earlier definition (I'm expanding it a little) [m] = {m +kp : k in Z} should do it :smile:

    (btw, always use squirly brackets for listing the elements of sets :wink:)
  6. Oct 21, 2010 #5
    thanks a lot !!!!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook