Congruences and Modular Arithmetic
Gauss's congruence notation turns questions about divisibility into arithmetic with finitely many residues. This unit builds that arithmetic, shows when a factor may be cancelled and which residues have an inverse, solves linear congruences and systems of them with the Chinese remainder theorem, computes large powers by repeated squaring, and explains the divisibility tests and the check digits of book numbers and bank accounts.
A clock that shows 11 o’clock will show 2 o’clock three hours later, and nobody is troubled that \(11 + 3\) is 14. The clock has forgotten the twelve. Arithmetic that forgets every multiple of a fixed number is the subject of this unit. Carl Friedrich Gauss (1777-1855) gave it a notation on the first page of his Disquisitiones Arithmeticae (1801), and with that notation the questions about divisibility of Units 2 and 3 become questions about finitely many remainders, which this unit calls residues, few enough to fit in a table. The unit builds this arithmetic, including the one operation that needs care, which is division. It then solves the equations that can be posed in this arithmetic, and it ends with the ways in which congruences quietly check book numbers and bank accounts.
1 Congruences and residue classes
Let \(n\) be a positive integer, called the modulus. Two integers \(a\) and \(b\) are congruent modulo \(n\) if \(n\) divides their difference, and this is written \(a \equiv b \pmod n\). For example, \(14 \equiv 2 \pmod{12}\) because \(12 \mid 14 - 2\), and \(-1 \equiv 11 \pmod{12}\) because \(12 \mid -1 - 11 = -12\). The notation is Gauss’s, and so are the words modulus and congruent; the first of the numbered articles into which that book is divided defines them exactly as above. When \(n\) does not divide \(a - b\), the integers are incongruent, written \(a \not\equiv b \pmod n\).
The two descriptions in the box agree for the following reason. Division with remainder writes \(a = qn + r\) and \(b = q'n + r'\) with remainders between \(0\) and \(n - 1\), so \(a - b = (q - q')n + (r - r')\), and \(r - r'\) lies strictly between \(-n\) and \(n\). If \(n\) divides \(a - b\), it also divides \(r - r' = (a - b) - (q - q')n\), and the only multiple of \(n\) that lies strictly between \(-n\) and \(n\) is 0, so \(r = r'\); and if \(r = r'\) then \(a - b = (q - q')n\) is a multiple of \(n\). A congruence therefore says that two numbers agree in their remainder and may differ by any multiple of \(n\), which is exactly what the clock face in Figure 1 forgets.
Three properties make the symbol \(\equiv\) behave like an equals sign.