Modular arithmetic is a generalization of odd and even. We say that two integers, x and y, are congruent modulo a third integer n if and only if x - y is divisible by n. For example, 5 and 8 are congruent modulo 3 because 5 - 8 = -3 is divisible by 3. However, 4 and 5 are not congruent modulo 3. A number is even if it is congruent to zero modulo two. It is odd if it is congruent to one modulo two. The notation "x y mod(n)" means "x is congruent to y modulo n." The notation gcd(m, n) means the greatest common divisor (or factor) of m and n.Here are the basic facts about modular arithmetic:

• if x y mod(n) and z w mod(n), then x + z y + w mod(n) and xz yw mod(n).
• if xm ym mod (n) and gcd(m, n) = 1 then...