Congruences

Definition: If n is a fixed positive number and a,{}b are integers then a is congruent to b (mod-n) if a-b is divisible by n. We write

The normal properties of subtraction, addition, multiplication, exponentiation are inherited from

So ifthenand

Congruence is an equivalence relation, since

so

soso

thenandthenhence

This means that for eachthe set of equivalence classes is the set

Ifthe set of equivalence classes is

Congruences may be used in the following ways using the above rules.

Show that 37^{37} +2 is divisible by 13.

Henceis divisible by 13.