We begin this section by reviewing the three different ways of thinking about congruence classes that were discussed in the Prelab section.
3.1.1 By Counting
Portions of the congruence classes modulo n can be viewed using the applet below. For example, here's what we get when n = 7:
Keep in mind that the output only shows part of each congruence class. Try changing the 7 to some other positive integers n to see the congruence classes modulo n.
3.1.2 By Differences Within Rows
Referring to the above description of congruence classes, we see that each number is exactly n more than the number to its left (where n is the number of rows). By extension, if we pick any number r and look c columns to the right, we will have to add n to r a total of c times. Thus, c columns directly to the right of r is the number r + cn. Therefore it follows that two numbers are in the same row if they differ by a multiple of n. Using the congruence notation introduced in the Prelab section, our observation may be expressed as follows:
b
(mod n) if and only if n | (b – a).
This characterization of congruence is extremely useful in proofs, since it brings everything known about divisibility into the picture and frequently reduces congruence problems to simple algebra.
3.1.3 By Remainders
In this section, we consider a third way to think about congruence classes. Recall that the Division Algorithm states that if any integer a is divided by a positive integer n, then the remainder r is always between 0 and n – 1. (Recall also our notation for the remainder: r = a % n.) The on-line calculator can be used to compute remainders. To get the remainder when a is divided by n, we just type in "a % n". The "%" symbol is used by many computer languages to denote the remainder operation. For example, 27 % 4 gives the remainder when 27 is divided by 4:
Can you predict the result of each of the following before executing it?
The next applet produces output similar to "Congruence Classes" above. The difference is that each entry is replaced by its remainder when divided by n. Here's what we get when n = 7:
Quite a striking pattern, isn't it? Try changing 7 to some other positive integers.
Research Question 1Form a conjecture that explains the output of "Congruence Classes modulo n."
|
3.1.4 Summing Up
Above we have considered three ways of looking at congruence modulo n. Each is useful in its own way. The first description is somewhat visual and gives a good intuitive feel for congruence classes. The description in terms of differences frequently works the best in proofs. The characterization in terms of remainders makes it easy to compute modulo n since there are only n integers (the remainders 0, 1, . . . , n – 1) to keep track of. (There will be more on computing modulo n later in the lab.)
3.1.5 A Tip
Mathematicians often think about and work with a concept in one way, but write their proofs in a different way. When reading proofs in a book, all one typically sees is the proof written in the most efficient manner, while the author may prefer to think about the problem in other terms. When there are several ways of describing the same thing, do not feel limited to work with only one of them. Learn how to use them all, so you can move back and forth between them depending on the situation.