Modular Arithmetic: Doing Maths on a Clock

If it is 10 o'clock and you wait 5 hours, it is 3 o'clock. You did not compute 15 and then apologise. You worked in a system where 15 and 3 are the same number, because only the remainder after dividing by 12 carries meaning.

Definition: Two integers are congruent modulo $n$ when they differ by a multiple of $n$, written $a \equiv b \pmod{n} \iff n \mid (a - b)$

So $15 \equiv 3 \pmod{12}$, and so do 27, 39 and $-9$. The notation is deliberately not an equals sign: these are genuinely different integers that this system declines to distinguish.

Everything that wraps around works this way: array indices in a ring buffer, hash buckets, days of the week, angles, fixed-width integer overflow, and the phase of a periodic signal.

Congruence mod $n$ is an equivalence relation: reflexive, symmetric, and transitive. Every equivalence relation partitions its set, and here the partition is into $n$ residue classes, one per possible remainder.

Working mod 5, every integer belongs to exactly one of five classes:

$\{\dots, -5, 0, 5, 10, \dots\},\ \{\dots, -4, 1, 6, 11, \dots\},\ \dots,\ \{\dots, -1, 4, 9, 14, \dots\}$

The set of those classes is written $\mathbb{Z}_n$, and it is a finite number system with $n$ elements in which you can add, subtract and multiply exactly as usual.

Key idea: This is why modular arithmetic is useful in computing. It replaces an infinite set with a finite one while keeping the arithmetic that matters, which is precisely what a fixed-width register does to the integers.

The operations respect congruence, which is the fact everything practical rests on:

$(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$ $(a \times b) \bmod n = ((a \bmod n) \times (b \bmod n)) \bmod n$

You may reduce at any point without changing the answer. That is not a convenience, it is what makes the arithmetic possible at all on bounded hardware.

# Overflows a 64-bit integer long before finishing, in C or Rust
result = 1
for x in values:
    result = result * x        # grows without bound
result %= n

# Stays below n^2 throughout, so it fits
result = 1
for x in values:
    result = (result * x) % n  # reduce every step

In practice: Python's arbitrary-precision integers hide this problem and then hand you a different one, since multiplying million-digit numbers is slow. Reducing every step is correct and fast in every language.

The ISBN case shows why the modulus is chosen rather than convenient. Eleven is prime, and that is exactly what makes every weighted-position error detectable: with a composite modulus, certain digit substitutions cancel out and slip through. Check-digit schemes with a prime modulus are strictly stronger, and that is the whole reason ISBN-10 needed an X for the value 10.

Mathematics defines the residue of $-7$ mod 3 as 2, because $-7 = (-3) \times 3 + 2$ and residues are taken in $\{0, 1, 2\}$. Programming languages disagree with each other about this.

-7 % 3        # Python:  2   (sign follows the divisor)

-7 % 3        /* C, Java, Go, Rust:  -1  (sign follows the dividend) */

Gotcha: In C-family languages, i = (i - 1) % n on a ring buffer produces $-1$ when i is 0, and indexing with it is undefined behaviour or an exception rather than the wraparound you wanted. The portable fix is ((i - 1) % n + n) % n, which costs one extra operation and works in every language including Python.

This is not a language defect so much as two defensible conventions, but it is a reliable source of off-by-one bugs at exactly the boundary where they are least likely to be tested.

Addition, subtraction and multiplication transfer to $\mathbb{Z}_n$ without incident. Division does not. Dividing by $a$ means multiplying by an inverse $a^{-1}$ with $a \cdot a^{-1} \equiv 1 \pmod n$, and such an element need not exist.

Mod 12, the number 3 has no inverse: $3 \times k$ cycles through $3, 6, 9, 0$ forever and never hits 1. Mod 26, however, $3^{-1} = 9$, since $27 \equiv 1$.

$a^{-1} \text{ exists mod } n \iff \gcd(a, n) = 1$

The condition is that $a$ and $n$ share no factor. Two immediate consequences: when $n$ is prime every non-zero element is invertible, so $\mathbb{Z}_p$ is a field and you can do ordinary algebra in it; when $n$ is composite it is not, and that asymmetry is why prime moduli appear wherever the arithmetic has to be well behaved.

Finding $\gcd(a, b)$ by factoring both numbers is hopeless for large inputs. Euclid's method never factors anything. It repeatedly replaces the pair with the smaller number and the remainder, using the fact that $\gcd(a, b) = \gcd(b, a \bmod b)$:

$1071 = 2 \times 462 + 147$ $462 = 3 \times 147 + 21$ $147 = 7 \times 21 + 0$

The last non-zero remainder, 21, is the gcd. Three steps on six-digit inputs.

It is fast because the remainder at least halves every two steps, giving a step count logarithmic in the input. The worst case is exactly consecutive Fibonacci numbers, a result of Lame from 1844:

Inputs grow by a factor of 15,000 across that chart and the work barely triples.

The extended Euclidean algorithm tracks the coefficients as it goes, producing $x$ and $y$ with

$ax + by = \gcd(a, b)$

When $\gcd(a, n) = 1$ this reads $ax + ny = 1$, so $ax \equiv 1 \pmod n$, and $x$ is the inverse you wanted. One algorithm answers both questions at once: whether an inverse exists, and what it is.

def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y

def inverse(a, n):
    g, x, _ = egcd(a, n)
    if g != 1:
        raise ValueError(f"{a} has no inverse mod {n}")
    return x % n

inverse(3, 26)      # 9
pow(3, -1, 26)      # 9  -- Python 3.8+ has this built in

Square-and-multiply works by reading the exponent in binary: repeatedly square the base, and multiply into the accumulator wherever the exponent has a 1 bit. A 2048-bit exponent costs about 3,000 modular multiplications rather than $2^{2048}$ of them.

Fermat's little theorem is the second lever:

$a^{p-1} \equiv 1 \pmod p \quad \text{for prime } p \text{ and } p \nmid a$

In practice: pow(base, exp, mod) in Python does square-and-multiply for you and is the only correct way to write this. Computing base ** exp % mod builds the full integer first and will hang the process for any realistic exponent.

Modular arithmetic supplies something rare: operations that are cheap forwards and, as far as anyone knows, expensive backwards.

• Computing $g^x \bmod p$ takes a few thousand multiplications.
• Recovering $x$ from $g^x \bmod p$, the discrete logarithm, has no known efficient method for well-chosen $p$.
• Multiplying two large primes is instant. Factoring the product back is not.

That gap is the entire basis of public-key cryptography, and it is a gap in what we currently know how to compute rather than a proven impossibility. If someone found a fast factoring algorithm tomorrow, the mathematics in this lesson would be unchanged and a great deal of infrastructure would not be.

How those hard problems become working key exchange, signatures and certificates is the subject of the separate Applied Modern Cryptography course in this catalogue. What this lesson gives you is the arithmetic underneath it: congruences, inverses, Euclid, and exponentiation that finishes.