They are all different (modulo ), because if with
then , and since , we get
, which is impossible.
Now, since all these numbers are different, the set
will have the possible congruenceclasses (although not necessarily in the same order) and therefore