3

Congruences

**3.1 Definitions**

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

Start Free Trial

No credit card required