1.6 — Modular Arithmetic: The Mathematics of Wrapping Around

It is 9 o'clock. What time is it in 7 hours? Everyone answers 4, instantly, without thinking of it as mathematics. But 9 + 7 = 16, and you did not say 16. You wrapped around.

That wrap-around is a complete and consistent arithmetic in its own right, and it turns out to be one of the most useful systems in the book — it runs your calendar, your card's check digit, your hash tables, your random-number generator and your encryption.

1. The definition

Fix a positive whole number m, called the modulus. Then a \bmod m is the remainder when a is divided by m.

17 \bmod 5 = 2, \qquad 30 \bmod 7 = 2, \qquad 100 \bmod 10 = 0

Two numbers are congruent modulo m when they leave the same remainder, written:

a \equiv b \pmod{m}

with three bars instead of two, read "a is congruent to b modulo m". So 17 \equiv 2 \pmod 5, and 9 + 7 = 16 \equiv 4 \pmod{12}, which is the clock.

An equivalent and often more useful way to say it: a \equiv b \pmod m exactly when m divides a - b. Check: 17 - 2 = 15, and 5 divides 15. This version is easier to work with in proofs, because it turns a statement about remainders into a statement about divisibility.

Congruence sorts every integer into m buckets, called residue classes. Modulo 5, the buckets are:

\{\ldots,-10,-5,0,5,10,\ldots\},\; \{\ldots,-9,-4,1,6,11,\ldots\},\; \ldots

five of them, labelled 0 through 4. The central idea of the whole chapter is that these buckets can be added and multiplied as if they were numbers, and that everything works.

Arithmetic modulo 12, drawn as the object everyone already owns. Adding means stepping clockwise; going past the top wraps to the start. The clock is not an analogy for modular arithmetic — it is modular arithmetic, and has been since Babylon. Image: Wikimedia Commons.

2. You can add and multiply before or after reducing

This is the property that makes modular arithmetic arithmetic rather than an occasional trick. If a \equiv a' and b \equiv b' \pmod m, then:

a + b \equiv a' + b' \pmod m \qquad\text{and}\qquad a \times b \equiv a' \times b' \pmod m

In practice: you may reduce at any point, as often as you like, and the answer is unchanged. That is what makes enormous computations feasible.

Worked example. What is 7^{100} \bmod 13?

Computing 7^{100} first would give an 85-digit number. Instead, reduce as you go.

7^2 = 49 \equiv 10 \pmod{13}

7^4 = (7^2)^2 \equiv 10^2 = 100 \equiv 9 \pmod{13}

7^{12} \equiv 1 \pmod{13} \quad \text{(a fact we justify in a moment)}

Since 100 = 8 \times 12 + 4:

7^{100} = (7^{12})^{8} \times 7^{4} \equiv 1^8 \times 9 = \mathbf{9} \pmod{13}

Every number stayed under 200. This technique — modular exponentiation — is the computational heart of RSA, where the exponents have hundreds of digits.

Why 7^{12} \equiv 1: that is Fermat's little theorem. If p is prime and a is not a multiple of p, then

a^{p-1} \equiv 1 \pmod p

Here p = 13, so 7^{12} \equiv 1. The theorem is from 1640 and is the engine inside RSA; Volume I, 8.2 shows how.

Division is the difficult one

Addition, subtraction and multiplication behave. Division does not, and the reason is instructive.

To divide by a you need a number x with a x \equiv 1 \pmod m — a modular inverse. Modulo 7, the inverse of 3 is 5, because 3 \times 5 = 15 \equiv 1. So "dividing by 3" modulo 7 means multiplying by 5.

But modulo 12, the number 3 has no inverse at all. Work through 3 \times 1, 3 \times 2, \ldots, 3 \times 11 modulo 12 and you get 3, 6, 9, 0, 3, 6, 9, 0, \ldots — never 1.

The rule: a has an inverse modulo m exactly when \gcd(a, m) = 1, that is, when they share no common factor. And \gcd(3, 12) = 3, so no inverse.

An immediate consequence: when m is prime, every nonzero number has an inverse, because a prime shares a factor with nothing below it. That is why cryptography almost always works modulo a prime — you get a system where you can divide, which mathematicians call a field and Chapter 8.4 discusses further.

Finding the inverse is done by running Euclid's algorithm from Chapter 1.5 backwards, a procedure called the extended Euclidean algorithm.

3. Divisibility rules, finally explained

You were taught these in school as magic. They are all one line of modular arithmetic.

Divisible by 9 if the digits sum to a multiple of 9.

Because 10 \equiv 1 \pmod 9, and therefore 10^k \equiv 1^k = 1 for every k. So a number like 3407 satisfies:

3407 = 3 \cdot 10^3 + 4 \cdot 10^2 + 0 \cdot 10 + 7 \equiv 3 + 4 + 0 + 7 = 14 \equiv 5 \pmod 9

Every power of ten collapses to 1, so the whole number collapses to its digit sum. 3407 leaves remainder 5, so it is not divisible by 9 — and you learned the shortcut without ever being told it was a congruence.

Divisible by 3: same argument, since 10 \equiv 1 \pmod 3 as well.

Divisible by 11 if the alternating digit sum is a multiple of 11. Here 10 \equiv -1 \pmod{11}, so 10^k \equiv (-1)^k — alternating +1, -1, +1, \ldots from the units column leftwards. For 3407: 7 - 0 + 4 - 3 = 8, not a multiple of 11.

Divisible by 4 if the last two digits are. Because 100 \equiv 0 \pmod 4, so every column from the hundreds up vanishes entirely.

Divisible by 8 if the last three digits are, for the same reason with 1000.

The old accountants' trick of casting out nines — checking a long addition by comparing digit sums — is exactly this rule used as an error detector. It is the direct ancestor of the checksums in the next section.

4. Check digits: modular arithmetic guarding your data

Every bank card number ends in a digit that is not part of the account number. It is computed from the others so that a typo produces an invalid number. The algorithm, from IBM in 1954 and named after Hans Peter Luhn, works like this.

From the rightmost digit moving left, double every second digit. If doubling gives something above 9, subtract 9 (equivalently, add the two digits). Sum everything. The card is valid only if the total is \equiv 0 \pmod{10}.

// Luhn check. Returns true if the digit string is self-consistent.
function luhnValid(cardNumber) {
  const digits = cardNumber.replace(/\D/g, '').split('').map(Number);
  let sum = 0;
  for (let i = 0; i < digits.length; i++) {
    let d = digits[digits.length - 1 - i];   // (1) walk from the right
    if (i % 2 === 1) {                        // (2) every second one
      d = d * 2;
      if (d > 9) d -= 9;                      // (3) fold 12 → 3, 18 → 9
    }
    sum += d;
  }
  return sum % 10 === 0;                      // (4) the modular test
}
luhnValid('4539 1488 0343 6467');             // → true
luhnValid('4539 1488 0343 6468');             // → false

Line (1) walks the digits right to left, because the doubling pattern is anchored at the last digit. Line (2) picks out alternate positions. Line (3) is the fold: doubling 6 gives 12, and 12 - 9 = 3, which is the same as summing the digits of 12. Line (4) is the whole test — a valid number is one whose weighted sum is a multiple of ten.

What it catches, and what it does not. Every single mistyped digit is caught, because changing one digit changes the sum by something not a multiple of 10. Almost every swap of two adjacent digits is caught. It does not catch swapping 09 for 90, and it is not security — anyone can compute a valid number. It is a typo filter, which is all it was built to be.

The same idea, with different weights and moduli, is your ISBN book number (mod 11), your shop barcode (mod 10), an IBAN bank code (mod 97), and India's Aadhaar number (using the Verhoeff algorithm, which catches more transpositions).

5. Hashing, cycling and pseudo-randomness

Hash tables. To store a key in one of m buckets, compute a number from the key and take it modulo m. That is the whole idea, and Volume I, 4.4 develops it. This is also why table sizes are often prime: if m shares a factor with a regular pattern in your keys, whole ranges of buckets go unused.

Pseudo-random numbers. The classic linear congruential generator is one line:

x_{n+1} = (a x_n + c) \bmod m

Pick a, c, m and a starting seed, and out comes a sequence that looks random. It is not random at all — it is completely determined by the seed, which is why the same seed reproduces the same "random" sequence, and why this is called pseudo-random. It also must eventually repeat, since there are only m possible values, so the sequence has a period. Choosing a, c, m badly gives a short period and visible patterns, which is a real historical embarrassment: IBM's RANDU generator from the 1960s produced points that all lay on 15 planes in three dimensions, quietly invalidating a decade of simulations.

Never use these for anything security-related. Volume I, 8.2 explains what to use instead.

Cycling through positions. Anything that wraps is modular: the day of the week, the frames of an animation, a circular buffer in memory, the pages of a carousel. The code is always index = (index + 1) % length.

The negative-number trap in programming

Mathematically, -1 \bmod 5 is 4 — you walk one step backwards from zero on a five-position clock. But in C, C++, Java, JavaScript and Go, -1 % 5 gives -1, because those languages define % as the remainder of truncated division rather than as the mathematical modulus. Python and Ruby give 4.

This produces a genuine class of bug: a carousel that goes to index -1 instead of wrapping to the last slide. The fix is ((n % m) + m) % m, which forces the result non-negative.

6. Calendars, which are modular arithmetic all the way down

The day of the week is arithmetic modulo 7. A common year is 365 = 52 \times 7 + 1 days, so 365 \equiv 1 \pmod 7 — each ordinary year shifts your birthday forward one weekday. A leap year has 366 \equiv 2, shifting it two.

Leap years are three nested modular conditions, and the reason for the nesting is that the year is not a whole number of days. It is about 365.2422 days.

• Divisible by 4: leap. This corrects 0.25 per year, slightly too much.
• Unless divisible by 100: not leap. This removes the overcorrection.
• Unless divisible by 400: leap after all. This puts back a little of what the previous rule removed.

So 1900 was not a leap year and 2000 was. The Gregorian result is 365 + \frac{1}{4} - \frac{1}{100} + \frac{1}{400} = 365.2425 days, off from the true value by about 27 seconds a year — one day of drift every 3,200 years.

When the reform happened in 1582, the accumulated error from the older Julian rule had to be removed all at once, so Thursday 4 October was followed by Friday 15 October. Britain and its colonies held out until 1752 and skipped eleven days. Volume I, 3.6.11 mentions why date handling in software is so full of traps; this is one of the reasons.

Every formula above, built from scratch

None of the results in this chapter are worth memorising, because each one can be rebuilt in under a minute from something simpler. What follows is that rebuilding, one result at a time, so the formula and the reason for it sit on the same page as the explanation that needed them.

Divisibility rules, and why they work

Everyone is taught these. Almost nobody is shown the reason, which is the same reason in every case: 10 leaves a predictable remainder when divided by the test number.

Divisible by 3 (or 9) if the digits add to a multiple of 3 (or 9)

Take the number 4,281. Written out in place value:

4281 = 4\cdot1000 + 2\cdot100 + 8\cdot10 + 1

Now the key observation: 10 = 9 + 1, 100 = 99 + 1, 1000 = 999 + 1. Every power of ten is a string of nines plus one. Substitute:

4281 = 4(999+1) + 2(99+1) + 8(9+1) + 1

= \underbrace{(4\cdot999 + 2\cdot99 + 8\cdot9)}_{\text{every term a multiple of 9}} + \underbrace{(4 + 2 + 8 + 1)}_{\text{the digit sum}}

The first bracket is divisible by 9 no matter what the digits are. So the whole number is divisible by 9 exactly when the digit sum is, and divisible by 3 exactly when the digit sum is, since 9 is a multiple of 3. Here the digit sum is 15, which is divisible by 3 but not 9 — so 4,281 is a multiple of 3 and not of 9. Checking: 4281 = 3 \times 1427.

Divisible by 11 if the alternating digit sum is

Now 10 = 11 - 1, so powers of ten alternate: 10 \equiv -1, 100 \equiv +1, 1000 \equiv -1 when working modulo 11. Reading the digits from the right and alternating the signs therefore tests divisibility by 11. For 4,281: 1 - 8 + 2 - 4 = -9, not a multiple of 11, so 4,281 is not either.

Divisible by 4 if the last two digits are

Every power of ten from 100 upwards is divisible by 4, because 100 = 4 \times 25. So everything above the tens column contributes nothing to the remainder, and only the last two digits matter. The same argument with 1000 = 8 \times 125 gives the rule for 8, and with 10 = 2 \times 5 gives the rules for 2 and 5.

Modular arithmetic

Write a \equiv b \pmod m — read "a is congruent to b, modulo m" — to mean m divides a - b, which is the same as saying they leave the same remainder on division by m.

The rules that make it useful. If a \equiv b and c \equiv d modulo m, then

a + c \equiv b + d, \qquad a - c \equiv b - d, \qquad ac \equiv bd \pmod m

Why multiplication survives. Write a = b + km and c = d + lm for whole numbers k, l. Multiply:

ac = bd + bl m + dkm + klm^2 = bd + m(bl + dk + klm)

Everything after bd carries a factor of m, so ac - bd is a multiple of m, which is exactly ac \equiv bd. This is why you can reduce numbers before multiplying instead of afterwards — the reason a computer can compute 7^{1000} \bmod 13 without ever forming the astronomically large 7^{1000}.

Fermat's little theorem

a^{p-1} \equiv 1 \pmod p \qquad \text{for prime } p \text{ and } a \text{ not a multiple of } p

Where it comes from. Take the numbers a, 2a, 3a, \ldots, (p-1)a and reduce each modulo p. Two claims:

1. None is 0. If p divided ka then, p being prime, it would have to divide k or a; but k < p and a is not a multiple of p.
2. No two are equal. If ia \equiv ja then p divides (i-j)a, and by the same reasoning p divides i - j; but i and j are both below p, so their difference is too small unless it is zero.

So these p-1 values are the numbers 1, 2, \ldots, p-1 in some shuffled order. Multiply the whole list together, both ways round:

a \cdot 2a \cdot 3a \cdots (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod p

The left side is a^{p-1}(p-1)! and the right is (p-1)!. Since (p-1)! shares no factor with p, it may be cancelled, leaving a^{p-1} \equiv 1.

A worked case. p = 7, a = 3. The theorem promises 3^6 \equiv 1 \pmod 7. Check: 3^6 = 729 = 7 \times 104 + 1. Correct.

Euler's theorem, the version RSA actually uses

a^{\phi(n)} \equiv 1 \pmod n \qquad \text{when } \gcd(a,n) = 1

Here \phi(n) — read "phi of n" — counts how many numbers from 1 to n share no factor with n. For a prime p every one of 1, \ldots, p-1 qualifies, so \phi(p) = p-1 and Euler's theorem collapses back to Fermat's. For a product of two distinct primes, which is the RSA case:

\phi(pq) = (p-1)(q-1)

Why. Of the pq numbers from 1 to pq, the ones sharing a factor are the multiples of p (there are q of them) and the multiples of q (there are p), and pq itself has been counted twice. So the count of good numbers is pq - q - p + 1, which factorises as (p-1)(q-1).

7. Where this shows up in your life

Every clock and calendar you read. Modulo 12, 24, 7, 60 and 365.

Every card payment. The Luhn digit is checked before the transaction is even sent.

Every ISBN, barcode and IBAN. Same principle, different modulus.

Every HTTPS handshake. RSA and Diffie–Hellman are modular exponentiation with huge moduli; Volume I, 8.2 works through them.

Every hash map, dictionary and object lookup in every program you have written.

Musical notes. Twelve semitones per octave, and transposing a melody is adding a constant modulo 12. Two notes an octave apart get the same name because they are congruent.

---

We now have the integers thoroughly understood: their signs, their fractions, their atoms, and their wrap-around arithmetic. What remains is the discovery that broke Greek mathematics — that the rationals, dense as they are, still have holes in them.