Four hours after twenty-three

Write the hours after 23 without stopping:

23, 24, 25, 26, 27, …

Now write what the clock displays:

23, 0, 1, 2, 3, …

The clock has not made $27$ equal to $3$ as integers. It has declared them equivalent for the purpose of hour-of-day: their difference, 24, is a whole number of revolutions. We write

$$27 \equiv 3 (mod 24).$$

More generally, $a \equiv b (mod n)$ exactly when $n$ divides $a-b$. Every integer belongs to one of $n$ equivalence classes, labeled by the remainders $0,1,\ldots,n-1$.

Reduce whenever you like

The useful miracle is compatibility. If $a \equiv a'$ and $b \equiv b'$ modulo $n$, then

$$a+b \equiv a'+b' (mod n)$$

and

$$ab \equiv a'b' (mod n).$$

For addition, subtract the right side from the left: $(a-a')+(b-b')$. Both pieces are multiples of $n$, so their sum is. Multiplication follows by writing $ab-a'b'=a(b-b')+b'(a-a')$.

That proof grants an engineering license: reduce before an operation, after it, or between every step. The final remainder cannot change. Large exponents become manageable by repeated squaring and reduction; ring-buffer indices become (index + 1) mod capacity; weekday arithmetic never leaves seven states.

The remainder classes support addition and multiplication, with $0$ and $1$ as identities and additive inverses obtained by walking around the circle backward. This is the ring of integers modulo $n$.

Division has a gate

On an ordinary calculator, divide by any nonzero number. On a clock, division means multiplying by an inverse. The inverse of $a$ modulo $n$ is a number $x$ satisfying

$$ax \equiv 1 (mod n).$$

Modulo 7, the inverse of 3 is 5 because $3\cdot5=15\equiv1$. Modulo 6, 3 has no inverse: its multiples visit only 0 and 3. The exact boundary is gcd(a,n) = 1. Bézout's identity proves it. If $ax+ny=1$, reducing modulo $n$ leaves $ax\equiv1$; conversely, an inverse gives such an integer equation.

denominator := modular(2, 7)
inverse_witness := modular(4, 7)
expect(denominator * inverse_witness == modular(1, 7))
inverse_witness

numerator := modular(3, 7)
denominator := modular(2, 7)
expect(denominator == modular(2, 7))
numerator / denominator

When $n$ is prime, every nonzero remainder is coprime to $n$, so every nonzero value has an inverse. The modular ring becomes a field. This is why prime moduli appear so often: division regains its ordinary shape everywhere except zero.

A check digit is a conserved remainder

Suppose a code chooses its final digit so the weighted digit sum is congruent to zero modulo 10. At the receiver, recompute the sum. A single changed digit usually changes the remainder, exposing damage. The check does not prove the message is correct—different damaged messages can share one remainder, as the pigeonhole chapter already guaranteed. It purchases a quantified class of detectable errors, not certainty.

The Luhn method, patented by IBM researcher Hans Peter Luhn, uses alternating weights and decimal digit sums so common transcription errors disturb the final congruence.

Where the circle runs out

• Modular equality always names its modulus. Omitting it changes the claim.
• Cancellation is unsafe without an inverse. From $ab\equiv ac$ one may cancel $a$ only when $a$ is invertible modulo $n$.
• Wraparound in machine integers resembles modular arithmetic, but language rules differ. Signed overflow may trap, wrap, or be undefined.
• A small checksum has unavoidable collisions. It detects a promised error family; it does not authenticate adversarial data.

Lessons

• Congruence groups integers by equal remainder.
• Addition and multiplication respect congruence, so reduction may happen at any point.
• A remainder is divisible only by values coprime to the modulus; prime moduli make every nonzero class invertible.
• Circular schedules, buffer indices, and check digits are the same algebra in different clothing.

Practice

1. Without looking back, compute $2^{10}$ modulo 7 by reducing after each squaring.
2. Explain why $2x\equiv2 (mod 6)$ has more than one solution and which failed cancellation would hide them.
3. A service rotates among 11 shards by request number modulo 11. Which shard receives request 10,000? Show a reduction that never handles a large number.
4. One day later, reconstruct the rule for modular invertibility from the phrase “shares no factor with the clock.”

The next question is about damage

A check digit can say that a word probably moved to the wrong remainder class. It usually cannot say which digit changed, much less repair it. To correct damage, valid messages must be placed far enough apart that a received word remains closest to only one of them. The next chapter turns redundancy into geometry.

References

1. Gauss. “Disquisitiones Arithmeticae.” 1801. — articles 1–12 introduce congruence systematically
2. Lehman, Leighton, Meyer. “Mathematics for Computer Science.” MIT OpenCourseWare, 2024. — the number-theory chapters prove the laws and Bézout's identity
3. Luhn. “Computer for Verifying Numbers.” US Patent 2,950,048, 1960. — the primary specification of the decimal checking method