Show that if S has b elements and no two elements of S are c

Show that if S has b elements and no two elements of S are congruent modulo b, then S is a complete residue system modulo b.

Solution

The integers p and q are said to be members of the same residue class (mod b) when they have the same principle remainder (mod b). Thus there are b residue classes (mod b), corresponding to the b principle remainders 0, 1, 2, ..., b-1. Further, p and q belong to the same residue class (mod b) iff p q (mod b). Any set of integers {a₁, a₂, ..., a_b} representing all the residue classes (mod b) is called a complete residue system (mod b).

If p and q are two arbitrary elements of S, then p is not congruent q (mod b), i.e. p –q is not divisible by b. Let S = {a₁, a₂, ..., a_b}. Thus, if a_i – a_j is not divisible by b for any arbitrary integers I and j varying from 1 to b ( with i j), then there can be b-1 principal remainder ( mod b) i.e. 1, 2, ..., b-1. varying from ( I to b). Since no two of a_i and a_j are divisible by b, all the a_i ‘s constitute a complete residue system modulo b.