A very important equivalence relation defined on the integers is called
*congruence modulo n*. It is important because of a form of arithmetic
that is associated with it. If you tell time using a twelve hour clock, or have
played a board game or worked with a computer then you have probably experienced
this type of arithmetic. For example, if it is now 10 o'clock in the morning
what time will it be in 7 hours? What you do is add 10 to 7 and get an answer
of 5 since you replace the answer by the remainder on division by 12. That is
we have 10+7 = 5 (but that's not quite the story).

Let **Z** denote the integers and let *n*
be a fixed positive integer. We define a relation on **Z** by
(mod *n*) if and only if *n* divides *i* - *j*. Here both the symbol
and the (mod *n*) are used to denote the relation. It is easy to
check that this is an equivalence relation on the integers. An equivalence
class consists of those integers which have the same remainder on division by
*n*. Of course when you divide an integer by *n*,the remainder
is one of the integers 0, 1, 2, , *n*-2, *n*-1. Thus we obtain a
natural choice for the equivalence class representatives.
The factor set would be
and by abuse of notation we write this
as . Do note that this is not our only choice
for a set of class representatives. For example, modulo 5, a set of
class representatives is {0,1,2,3,4} but so too is {32,19,25,51,3003}.

For this important equivalence relation there is some other terminology that is
used. The equivalence classes are also known as
*congruence classes modulo n*. Rather than say the integers *i* and
*j* are equivalent we say that they are congruent modulo n which, symbollically,
is written as (mod *n*). The set of class representatives is
called a *complete set of residues modulo n* and a class representative
is called a *residue*.

One reason this is an important equivalence relation is because of being able
to do arithmetic on the factor set. In the integers we can add and multiply
elements together. These two arithmetic operations give rise to arithmetic
operations on the the factor set (i.e. the congruence classes modulo *n*).
We define [*i*] + [*j*] = [*i*+*j*] and [*i*][*j*] = [*ij*]. These rules are well
defined (independent of the choice of class representative). By our abuse
of notation we would drop the square brackets around the representative
realizing that *i*+*j* and *ij* are residues rather than
their value in the integers.

Now all of the above discussion is a little formal (and probably confusing).
In practice we just do weird arithmetic in the integers and not worry about
factor sets. We just have to realize that any number can be reduced to a
number between 0 and *n*-1 (or whatever residues you are using).
In other words we only keep track of remainders
on division by *n*. Oh, and also we can only use = with this wierd
arithmetic when we are in the factor set. Back in the integers we must use
along with (mod *n*). As an example, suppose that we are doing
arithmetic modulo 5. Then in the integers we have (mod 5)
(since 3 2 is 6 and that has a remainder of 1 on division by 5)
and (mod 5) (since 13 is congruent to 3 mod 5 as is 73; 3 added
to 3 is 6 which is congruent to 1 mod 5).
In the factor set these would have been
[3] [2] = [1] and [3]+[3] = 1. Note that 13 in the integers got
replaced by its equivalence class [3] in the factor set.
Try out this quiz on modular arithmetic.
You can try this quiz as often as you like without the questions repeating.
This way you can get lots of practice.

Wed Nov 20 00:52:35 PST 1996