O'Reilly logo

Elementary Number Theory with Programming by Jeanine Meyer, Marty Lewinter

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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.

Start Free Trial

No credit card required