Finding the no of equivalent classes

[commutator]

Homework Statement

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

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

 

[tiny-tim]

hi commutator!

(have a ± )

… the equivalent class of m consists of elements of the type
m +k p where k = 0,+/-1,+/-2...

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? ​

 

[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?

 

[tiny-tim]

hi commutator!

… 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?

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 )

 

[commutator]

thanks a lot !