Modular arithmetic sheds light on the relation of integers to their remainders when they are divided by a given positive integer. It is useful in both number theory and computer science.

The integers behave in a *periodic* way when we examine their expressions as one of the forms, for example, 3*n*, 3*n* + 1, and 3*n* + 2. Every third integer is a multiple of 3 and can therefore be written 3*n* for some integer *n*. Thus, 3 = 3 × 1, 6 = 3 × 2, 9 = 3 × 3, 12 = 3 × 4, and so on. On the other hand, the numbers 4, 7, 10, 13, etc. can be written 3*n* + 1, since they are one more than some multiple of 3. Similarly, 5, 8, 11, 14, etc. can be written 3*n* + 2. Thus, the sequence of consecutive numbers 3, 4, 5 yield numbers of the form 3*n*, 3*n* + 1, and 3*n* + 2. The next number, 6, signifies that the pattern repeats. In fact, the next three numbers, 6, 7, 8, mimic their three predecessors perfectly, following the same format as 3*n*, 3*n* + 1, 3*n* + 2. Of course, the *n* changes from 1 to 2, but the pattern persists. Every third number is of the same format.

There are three *classes* of numbers: 3*n*, 3*n* + 1, and 3*n* + 2. All numbers belong to one of these mutually exclusive and jointly exhaustive classes. Even 0 is a member of one of the classes, namely, the 3*n* class. Negative numbers are included, as well, since *n* may be negative.

The entire analysis can be repeated for the coefficient 5 or any other coefficient. Every integer is in one of the forms 5*n*, 5*n* + 1, 5 ...

Start Free Trial

No credit card required