Given integers a,b, and n with n > 0, we say that a and b are congruent modulo n if a-b is divisible by n, that is, if [(a-b)/( n)] is an integer. We write

a ºb (mod n)

if a and b are congruent modulo n>. Let a,b,c, and d be integers such that a ºc  (mod  n) and b ºd  (mod  n). It is not difficult to prove that

a+b º c+d (mod n)

(1)

and

a b º c d (mod n).

(2)

Given a fixed integer n > 0, called the modulus, we may form congruence classes of integers modulo n. Each congruence class is formally a set of the form

[a]: = a + n Z = { ¼, a-2n, a-n, a, a+n, a+2n, ¼}.

By (1) and (2), addition and multiplication of congruence classes is well-defined. More precisely, we define [a]+[b] = [a+b] and [a] ·[b] = [ab]. It is convenient to identify the element [a] with the smallest nonnegative number a¢ such that a º a¢ (mod  n) . This number a¢ will be denoted a  mod  n . For example, 13  mod  5 = 3. Let Z_n denote the set of congruence classes modulo n. For example, Z₅ = {0,1,2,3,4}.

The greatest common divisor (gcd) of two integers m and n is the greatest positive integer d such that d divides both m and n. For example, gcd(91,52) = 13. The Euclid algorithm states that if gcd(m,n) = d, then there are integers r and s such that mr + ns = d. In particular, the equation

mx º b (mod n) Û mx = b  (in Zn)

(3)

has a solution x if and only if b is divisible by d.

Let Z_n^* be the set of integers (congruence classes modulo n) k Î {1, ¼, n-1} with the property that gcd(k,n) = 1. For example, Z₁₂^* = {1,5,7,11}.