Finding the no of equivalent classes

1. Oct 21, 2010

commutator

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. Oct 21, 2010

tiny-tim

hi commutator!

(have a ± )
that's right!

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

if p = 10, what are the equivalence classes?

3. Oct 21, 2010

commutator

thanks . that was really encouraging.

for p=10, i got something like [-1]=(.....,-11,-21-1,9,19,29......)
[0]=(....-10,-20.....0,10,20,.....)
[1]=(...-29,-19....1,11,21,31...]
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?

4. Oct 21, 2010

tiny-tim

hi commutator!
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

(btw, always use squirly brackets for listing the elements of sets )

5. Oct 21, 2010

commutator

thanks a lot !!!!