The opening page of the first scroll of the Sunzi Suanjing in a Qing dynasty printed edition, with columns of Chinese characters inside a printed frame
Unit 04 · All masterclasses · 60 min

Congruences and Modular Arithmetic

Arithmetic on a clock: residues, inverses, linear congruences, and the Chinese remainder theorem
Image: Wikimedia Commons, public domain

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.

Preview: the beginning of the unit

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.

The twelve residues modulo 12 arranged as a clock face, with 12 o’clock written as 0. Five hours after 9 o’clock the hand points to 2, because \(9 + …
Figure 1. The twelve residues modulo 12 arranged as a clock face, with 12 o’clock written as 0. Five hours after 9 o’clock the hand points to 2, because \(9 + 5 = 14 \equiv 2 \pmod{12}\). The clock forgets every full turn, as a congruence forgets every multiple of the modulus.

Three properties make the symbol \(\equiv\) behave like an equals sign.

The full unit is part of the program

Want to see a complete unit first? Unit 3, Prime Numbers and Unique Factorization, is free to read.