Prove that the distinct equivalence classes in are precisely . Use the Division Algorithm.
Clearly for each . Now let . By the Division Algorithm, we have for some with . Thus .
Finally, note that the are distinct as follows. Suppose with and . Then , so for some , giving . But we also have , and both and are less than . So by the uniqueness part of the division algorithm we have , hence , a contradiction.
Thus the distinct equivalence classes in are precisely .