## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

3

Congruences

3.1 Definitions

Suppose that a, b are integers and that n is a natural number. By ab (mod n) one means n divides ba; 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 aa (mod n) and bb (mod n) then a + ba + b and abab (mod n). Further, we have abab (mod n), since n divides (aa)b + a(bb). Furthermore, if f (x) is any polynomial with integer coefficients, ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required