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

ncan be viewed using the applet below. For example, here's what we get whenn= 7:Keep in mind that the output only shows part of each congruence class. Try changing the 7 to some other positive integers

nto see the congruence classes modulon.## 3.1.2 By Differences Within Rows

Referring to the above description of congruence classes, we see that each number is exactly

nmore than the number to its left (wherenis the number of rows). By extension, if we pick any numberrand lookccolumns to the right, we will have to addntora total ofctimes. Thus,ccolumns directly to the right ofris the numberr+cn. Therefore it follows that two numbers are in the same row if they differ by a multiple ofn. Using the congruence notation introduced in the Prelab section, our observation may be expressed as follows:ab(modn) if and only ifn| (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

ais divided by a positive integern, then the remainderris always between 0 andn– 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 whenais divided byn, 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 whenn= 7:Quite a striking pattern, isn't it? Try changing 7 to some other positive integers.

## Research Question 1

Form 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 modulonsince there are onlynintegers (the remainders 0, 1, . . . ,n– 1) to keep track of. (There will be more on computing modulonlater 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.

Section 3.1 | Section 3.2 | Section 3.3 | Section 3.4

Copyright © 2001 by W. H. Freeman and Company