Suppose that a, b are integers and that n is a natural number. By a ≡ b (mod n) one means n divides b − a; and one says that a is congruent to b modulo n. If 0 ≤ b < n then one refers to b as the residue of a (mod n). It is readily verified that the congruence relation is an equivalence relation; the equivalence classes are called residue classes or congruence classes. By a complete set of residues (mod n) one means a set of n integers, one from each residue class (mod n).
It is clear that if a ≡ a′ (mod n) and b ≡ b′ (mod n) then a + b ≡ a′ + b′ and a − b ≡ a′ − b′ (mod n). Further, we have ab ≡ a′b′ (mod n), since n divides (a − a′)b + a′(b − b′). Furthermore, if f (x) is any polynomial with integer coefficients, ...