## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# 5MODULAR ARITHMETIC

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.

## CONGRUENCE CLASSES MOD k

The integers behave in a periodic way when we examine their expressions as one of the forms, for example, 3n, 3n + 1, and 3n + 2. Every third integer is a multiple of 3 and can therefore be written 3n 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 3n + 1, since they are one more than some multiple of 3. Similarly, 5, 8, 11, 14, etc. can be written 3n + 2. Thus, the sequence of consecutive numbers 3, 4, 5 yield numbers of the form 3n, 3n + 1, and 3n + 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 3n, 3n + 1, 3n + 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: 3n, 3n + 1, and 3n + 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 3n 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 5n, 5n + 1, 5 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required