Modular Arithmetic: Clock Maths, Congruences and the Rules That Make It Work

If it is 9 o'clock now, what time will it be in 5 hours? Two o'clock, not fourteen. A clock counts around a circle of 12 and starts again, and modular arithmetic is the mathematics of exactly that: arithmetic where only the remainder matters. Applied Discrete Structures makes the same comparison: the hours of the day are counted mod 12, except that 12 stands in for 0, and military time uses mod 24.

Congruence

Fix a positive integer n, the modulus. Two integers a and b are congruent modulo n, written

a ≡ b (mod n),

when they leave the same remainder on division by n. Levin's Discrete Mathematics: An Open Introduction uses that definition and notes that many books use an equivalent one instead: n divides a − b. Both say the same thing, and switching between them is often the key step in a proof.

Examples.

• 17 ≡ 2 (mod 5): both leave remainder 2, and 17 − 2 = 15 is divisible by 5.
• 100 ≡ 0 (mod 4): 4 divides 100.
• −3 ≡ 2 (mod 5): −3 + 5 = 2, and 5 divides −3 − 2 = −5.

Congruence mod n is an equivalence relation, reflexive, symmetric and transitive, so it splits the integers into n remainder classes. The guide to equivalence relations and classes shows the classes for mod 3. Applied Discrete Structures collects one representative from each class into ℤₙ = {0, 1, …, n − 1}, the integers modulo n.

The rules that make it useful

If a ≡ b and c ≡ d (mod n), then

• a + c ≡ b + d (mod n),
• a − c ≡ b − d (mod n),
• a · c ≡ b · d (mod n),
• aᵏ ≡ bᵏ (mod n) for every positive integer k.

In practice this means you may reduce mod n at any point in a calculation built from adding, subtracting and multiplying. Numbers never need to get large.

Example. What is 1,234 × 5,678 mod 9? Reduce first: 1,234 ≡ 1 (mod 9) and 5,678 ≡ 8 (mod 9), using digit sums. So the product is ≡ 1 × 8 = 8 (mod 9). The digit-sum shortcut is itself a modular fact, explained in why divisibility rules work.

Division is the exception

You cannot cancel freely. In mod 10,

2 × 3 = 6 and 2 × 8 = 16 ≡ 6, so 2 × 3 ≡ 2 × 8 (mod 10),

but 3 ≢ 8 (mod 10). The 2 cannot be cancelled because 2 and 10 share a factor.

Cancelling a is safe exactly when a has a multiplicative inverse mod n, a number a′ with a·a′ ≡ 1 (mod n), and that happens exactly when gcd(a, n) = 1. Applied Discrete Structures reflects this: every element of ℤₙ has an additive inverse (n − a for a ≠ 0), but its multiplicative group of integers modulo n keeps only the elements k with gcd(n, k) = 1. Finding inverses uses the Euclidean algorithm and is worked through in modular inverses.

Solving a congruence. Solve 4x ≡ 3 (mod 7). Since 4 × 2 = 8 ≡ 1, the inverse of 4 is 2. Multiply both sides by 2: x ≡ 6 (mod 7). Check: 4 × 6 = 24 = 3 × 7 + 3. When the modulus is small, trying each remainder in turn also works; Levin's book shows that trial-and-error approach alongside the algebraic one, which is simpler when the modulus is larger.