3 - Congruences

Summary

Let a, b ∈ ℤ and let m be a positive integer. We say that a and b are congruent modulo m, and we write

a ≡ b (mod m),

if m | (a − b). Observe that congruence modulo m is an equivalence relation. A residue class modulo m is a set consisting of all integers that are congruent to each other modulo m, i.e. that leave the same residue when divided by m. We usually denote a residue class by its smallest non-negative element. As an example, the numbers 3, 10, 38, −11, … belong to the residue class 3 modulo 7. For m ≥ 2 we denote by ℤ/mℤ the ring of the residue classes modulo m.

We start by describing a simple application of residue classes: the ISBN (International Standard Book Number) code, which can be found on the back cover of every fairly recent book. The code consists of 10 digits if the book was printed before January 1st, 2007, otherwise it consists of 13 digits. Let us describe the 10-digit code. Clearly the ISBN code has been created to identify each book in a unique way. As an example, the book Trigonometric Series by Antoni Zygmund (Cambridge University Press) has ISBN 0-521-35885-X. The code is divided into four groups. The first group identifies a country, a geographical area or a language area. In this case 0 denotes the English-speaking area. The second and third group, respectively, identify the publisher and the title. The last one is the check digit.