Two integers are congruent mod n if they have the same remainder when divided by n. This single equivalence relation turns the integers into a finite arithmetic system where addition, subtraction, and multiplication all work.
Modular arithmetic
We write a ≡ b (mod n) when n divides (a - b). The integers split into n congruence classes: [0], [1], ..., [n-1]. Arithmetic on these classes is well-defined: you can add, subtract, and multiply representatives and the class of the result does not depend on which representatives you chose.
Scheme
; Modular arithmetic
(define (mod-add a b n) (modulo (+ a b) n))
(define (mod-mul a b n) (modulo (* a b) n))
(display "7 + 8 mod 12 = ") (display (mod-add 7812)) (newline)
(display "5 * 7 mod 12 = ") (display (mod-mul 5712)) (newline)
; Congruence classes mod 5:; [0] = ..., -10, -5, 0, 5, 10, ...; [1] = ..., -9, -4, 1, 6, 11, ...; [2] = ..., -8, -3, 2, 7, 12, ...; [3] = ..., -7, -2, 3, 8, 13, ...; [4] = ..., -6, -1, 4, 9, 14, ...
(display "17 mod 5 = ") (display (modulo 175)) (newline)
(display "17 and 7 congruent mod 5? ")
(display (= (modulo 175) (modulo 75)))
Python
# Modular arithmeticdef mod_add(a, b, n): return (a + b) % n
def mod_mul(a, b, n): return (a * b) % n
print(f"7 + 8 mod 12 = {mod_add(7, 8, 12)}")
print(f"5 * 7 mod 12 = {mod_mul(5, 7, 12)}")
print(f"17 mod 5 = {17 % 5}")
print(f"17 and 7 congruent mod 5? {17 % 5 == 7 % 5}")
Solving linear congruences
The equation ax ≡ b (mod n) has a solution if and only if gcd(a, n) divides b. When it does, the extended Euclidean algorithm finds x. If gcd(a, n) = 1, then a has a multiplicative inverse mod n.
Scheme
; Solve ax = b (mod n) using extended GCD
(define (extended-gcd a b)
(if (= b 0)
(list a 10)
(let* ((result (extended-gcd b (modulo a b)))
(g (car result))
(x1 (cadr result))
(y1 (caddr result)))
(list g y1 (- x1 (* (quotient a b) y1))))))
(define (solve-congruence a b n)
(let* ((result (extended-gcd a n))
(g (car result))
(x0 (cadr result)))
(if (= 0 (modulo b g))
(modulo (* x0 (quotient b g)) n)
#f))) ; no solution; Solve 3x = 1 (mod 7) -- find inverse of 3 mod 7
(display "3x = 1 (mod 7): x = ")
(display (solve-congruence 317)) (newline)
; Check: 3*5 = 15 = 2*7 + 1; Solve 4x = 2 (mod 6)
(display "4x = 2 (mod 6): x = ")
(display (solve-congruence 426)) (newline)
; Solve 6x = 3 (mod 9)
(display "6x = 3 (mod 9): x = ")
(display (solve-congruence 639))
Neighbors
→ Abstract Algebra Ch.1 — the integers mod n form a group under addition (and a ring under addition and multiplication)