Congruences and modular arithmetic

In 1801 the 24-year-old Carl Friedrich Gauss published the Disquisitiones Arithmeticae, the book that turned number theory into a systematic science. Its first pages introduce a notation that seems almost trivial, \(a \equiv b \pmod n\), and the rest of the book shows how much it can do. Congruence lets us calculate with remainders as if they were numbers, and so replaces arguments about divisibility with algebra. This lesson sets up the arithmetic of congruences; the rest of the course runs on it.

Congruence

Definition. Let \(n\) be a positive integer. Integers \(a\) and \(b\) are congruent modulo \(n\), written \[a \equiv b \pmod n,\] if \(n \mid a - b\). The number \(n\) is the modulus. If \(n \nmid a - b\) we write \(a \not\equiv b \pmod n\).

For example \(38 \equiv 14 \pmod{12}\) because \(12 \mid 24\); \(-3 \equiv 9 \pmod{12}\); and \(17 \not\equiv 4 \pmod 6\) because \(6 \nmid 13\). Every integer is congruent to 0 or 1 modulo 2, according as it is even or odd. A congruence modulo 1 always holds and is useless, so from now on \(n \ge 2\).

Theorem. \(a \equiv b \pmod n\) if and only if \(a\) and \(b\) leave the same remainder on division by \(n\). In particular, every integer is congruent modulo \(n\) to exactly one of \(0, 1, \ldots, n - 1\), namely its remainder.

Proof. Write \(a = qn + r\) and \(b = q'n + r'\) with \(0 \le r, r' < n\). Then \(a - b = (q - q')n + (r - r')\), so \(n \mid a - b\) if and only if \(n \mid r - r'\). Since \(-n < r - r' < n\), that happens only when \(r = r'\).

The everyday example is the clock. Eight hours after 7 o'clock it is 3 o'clock, because \(7 + 8 = 15 \equiv 3 \pmod{12}\). Days of the week work modulo 7, minutes modulo 60, and angles modulo 360 degrees.

Congruence is an equivalence relation

Theorem. For a fixed modulus \(n\), congruence is reflexive (\(a \equiv a\)), symmetric (\(a \equiv b\) implies \(b \equiv a\)) and transitive (\(a \equiv b\) and \(b \equiv c\) imply \(a \equiv c\)). Proof: \(n \mid 0\); if \(n \mid a - b\) then \(n \mid b - a\); and if \(n \mid a - b\) and \(n \mid b - c\) then \(n\) divides the sum \(a - c\).

An equivalence relation partitions the integers into classes. The residue class of \(a\) modulo \(n\) is \[[a] = \{b : b \equiv a \pmod n\} = \{a + kn : k \in \mathbb{Z}\}.\] There are exactly \(n\) classes, \([0], [1], \ldots, [n - 1]\), and every integer lies in exactly one of them. The set of classes is written \(\mathbb{Z}/n\mathbb{Z}\) or \(\mathbb{Z}_n\).

A set of \(n\) integers containing one element from each class is a complete residue system modulo \(n\). The standard one is \(\{0, 1, \ldots, n - 1\}\), the least nonnegative residues. Another useful one is the least absolute residues, such as \(\{-2, -1, 0, 1, 2\}\) modulo 5 or \(\{-3, \ldots, 3\}\) modulo 7. Any \(n\) integers that are pairwise incongruent form a complete residue system: for instance \(\{0, 3, 6, 9, 12\}\) modulo 5, which reduces to \(\{0, 3, 1, 4, 2\}\).

Arithmetic with congruences

Congruences can be added, subtracted and multiplied like equations.

Theorem. If \(a \equiv b \pmod n\) and \(c \equiv d \pmod n\), then \[a + c \equiv b + d, \qquad a - c \equiv b - d, \qquad ac \equiv bd \pmod n.\] Consequently \(a^k \equiv b^k \pmod n\) for every \(k \ge 1\), and \(f(a) \equiv f(b) \pmod n\) for every polynomial \(f\) with integer coefficients.

Proof. Write \(a = b + sn\) and \(c = d + tn\). Then \(a + c = b + d + (s + t)n\), and \[ac = bd + (bt + ds + stn)n.\] The statement about powers follows by induction, and the statement about polynomials by combining sums and products.

This theorem means that addition and multiplication of classes, \([a] + [b] = [a + b]\) and \([a][b] = [ab]\), are well defined: the answer does not depend on which representatives we pick. So \(\mathbb{Z}_n\) is a number system in its own right, a commutative ring in the language of MATH-323. Here are its tables for \(n = 5\):

The practical power of the theorem is that we may reduce at every step. To find the last digit of \(7^{100}\), work modulo 10: \(7^2 = 49 \equiv -1\), so \(7^4 \equiv 1\), and \(7^{100} = (7^4)^{25} \equiv 1 \pmod{10}\). The last digit is 1, found without computing an 85-digit number. To show \(2^{20} - 1\) is divisible by 41: \(2^5 = 32 \equiv -9\), \(2^{10} \equiv 81 \equiv -1\), and \(2^{20} \equiv 1 \pmod{41}\).

Division needs care

Cancellation is the one rule of ordinary algebra that does not carry over. \(2 \cdot 3 \equiv 2 \cdot 8 \pmod{10}\), since \(6 \equiv 16\), but \(3 \not\equiv 8 \pmod{10}\). The problem is that 2 shares a factor with 10. And in \(\mathbb{Z}_{10}\) there are zero divisors: \(2 \cdot 5 \equiv 0\) although neither factor is \(\equiv 0\).

Theorem (cancellation). If \(ac \equiv bc \pmod n\) and \(\gcd(c, n) = 1\), then \(a \equiv b \pmod n\). More generally, if \(d = \gcd(c, n)\), then \(ac \equiv bc \pmod n\) implies \(a \equiv b \pmod{n/d}\).

Proof. \(n \mid (a - b)c\). Dividing through by \(d\): \((n/d) \mid (a - b)(c/d)\), and \(\gcd(n/d, c/d) = 1\), so Euclid's lemma gives \((n/d) \mid a - b\). In the example, \(\gcd(2, 10) = 2\) and \(3 \equiv 8 \pmod 5\) is indeed true.

Closely related: \(c\) has a multiplicative inverse modulo \(n\), an integer \(c'\) with \(cc' \equiv 1 \pmod n\), exactly when \(\gcd(c, n) = 1\). If \(\gcd(c, n) = 1\), Bézout gives \(cx + ny = 1\), so \(cx \equiv 1\). Conversely \(cc' = 1 + kn\) shows any common divisor of \(c\) and \(n\) divides 1. So when \(p\) is prime, every nonzero class modulo \(p\) is invertible, as the table above shows for \(p = 5\), and \(\mathbb{Z}_p\) is a field. The next lesson uses inverses to solve linear congruences.

Divisibility tests in one line

Congruences make the digit tests of lesson 1 immediate. Write \(n = \sum d_i10^i\). Since \(10 \equiv 1 \pmod 9\), \(n \equiv \sum d_i \pmod 9\). Since \(10 \equiv -1 \pmod{11}\), \(n \equiv \sum (-1)^id_i \pmod{11}\). Since \(1000 \equiv -1 \pmod{1001}\) and \(1001 = 7 \cdot 11 \cdot 13\), the alternating sum of blocks of three digits tests for 7, 11 and 13 simultaneously: for \(n = 1{,}234{,}567{,}890\), the alternating block sum is \(890 - 567 + 234 - 1 = 556\), and \(556 = 7 \cdot 79 + 3\), so \(n \equiv 3 \pmod 7\).

Casting out nines, an old bookkeeper's check, works the same way: to check \(4568 \times 7391 = 33{,}762{,}088\), reduce modulo 9: \(4568 \equiv 5\), \(7391 \equiv 2\), \(5 \cdot 2 = 10 \equiv 1\), and \(33{,}762{,}088 \equiv 3 + 3 + 7 + 6 + 2 + 0 + 8 + 8 = 37 \equiv 1\). The check passes. (It cannot catch errors that change the answer by a multiple of 9, such as swapping two digits.)

Check digits

Congruences protect data every day. A Canadian or American bank card number satisfies the Luhn condition: double every second digit from the right, add the digits of the results, and the total must be \(\equiv 0 \pmod{10}\). This catches every single-digit error and most swaps of adjacent digits. The ten-digit ISBN used for books before 2007 chooses its last digit \(d_{10}\) so that \[\sum_{i=1}^{10} i\,d_i \equiv 0 \pmod{11},\] writing X for 10. Because 11 is prime, this catches every single-digit error (changing \(d_i\) by \(e \not\equiv 0\) changes the sum by \(ie \not\equiv 0\)) and every transposition of two digits (swapping \(d_i\) and \(d_j\) changes the sum by \((j - i)(d_i - d_j)\), which is nonzero modulo the prime 11 unless the digits are equal). The modern ISBN-13 uses weights 1, 3, 1, 3, … modulo 10, which misses some transpositions; the prime modulus was better mathematics.

The day of the week

Calendars are arithmetic modulo 7. Since \(365 = 52 \cdot 7 + 1\), a date moves forward one weekday each ordinary year and two after a February 29. Zeller's congruence packages the rules of the Gregorian calendar into one formula; the program below uses it to find the weekday of any date. As a check by hand: 1 January 2000 was a Saturday. From then to 1 January 2026 are 26 years containing 7 leap days (2000, 2004, …, 2024), a shift of \(26 + 7 = 33 \equiv 5 \pmod 7\) weekdays, so 1 January 2026 fell on Saturday + 5 = Thursday.

Congruences by computer

The program prints the multiplication table modulo 6 to show zero divisors, lists the invertible classes modulo 12 and their inverses, verifies ISBN and Luhn check digits, and computes days of the week with Zeller's congruence.

import math

n = 6
print("multiplication mod 6:")
for a in range(n):
    print("  ", [a * b % n for b in range(n)])

units = {a: next(b for b in range(12) if a * b % 12 == 1) for a in range(12) if math.gcd(a, 12) == 1}
print("units mod 12 and inverses:", units)
print("pow(7, -1, 40) =", pow(7, -1, 40), " check:", 7 * pow(7, -1, 40) % 40)

def isbn10_ok(s):
    d = [10 if c == "X" else int(c) for c in s if c.isdigit() or c == "X"]
    return sum((i + 1) * x for i, x in enumerate(d)) % 11 == 0

def luhn_ok(s):
    digits = [int(c) for c in s if c.isdigit()][::-1]
    total = 0
    for i, x in enumerate(digits):
        if i % 2:
            x = 2 * x
            x = x - 9 if x > 9 else x
        total += x
    return total % 10 == 0

print("ISBN 0-306-40615-2 valid:", isbn10_ok("0-306-40615-2"), "| with a typo:", isbn10_ok("0-306-40651-2"))
print("Luhn 4539 1488 0343 6467 valid:", luhn_ok("4539 1488 0343 6467"), "| with a typo:", luhn_ok("4539 1488 0343 6468"))

def weekday(y, m, d):
    if m < 3:
        m, y = m + 12, y - 1
    K, J = y % 100, y // 100
    h = (d + 13 * (m + 1) // 5 + K + K // 4 + J // 4 + 5 * J) % 7
    return ["Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"][h]

for date in [(2000, 1, 1), (2026, 1, 1), (1867, 7, 1), (1776, 7, 4), (1969, 7, 20)]:
    print(date, weekday(*date))
print("last digit of 7^100:", pow(7, 100, 10), "  2^20 - 1 mod 41:", (2**20 - 1) % 41)

multiplication mod 6:
   [0, 0, 0, 0, 0, 0]
   [0, 1, 2, 3, 4, 5]
   [0, 2, 4, 0, 2, 4]
   [0, 3, 0, 3, 0, 3]
   [0, 4, 2, 0, 4, 2]
   [0, 5, 4, 3, 2, 1]
units mod 12 and inverses: {1: 1, 5: 5, 7: 7, 11: 11}
pow(7, -1, 40) = 23  check: 1
ISBN 0-306-40615-2 valid: True | with a typo: False
Luhn 4539 1488 0343 6467 valid: True | with a typo: False
(2000, 1, 1) Saturday
(2026, 1, 1) Thursday
(1867, 7, 1) Monday
(1776, 7, 4) Thursday
(1969, 7, 20) Sunday
last digit of 7^100: 1   2^20 - 1 mod 41: 0

Python's built-in pow(a, k, n) computes \(a^k \bmod n\) efficiently, and pow(a, -1, n) returns an inverse when one exists. The ISBN check catches the transposed digits 1 and 5, and the Luhn check catches the changed last digit. Canada's Confederation, on 1 July 1867, fell on a Monday.