Up: NOTES ON RELATIONS Previous: Equivalence relations

# Congruence modulo n

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.

Up: NOTES ON RELATIONS Previous: Equivalence relations

Peter Williams
Wed Nov 20 00:52:35 PST 1996