Modular Arithmetic

Division with remainder

Before decimals, everyone learned division as "how many times does it fit, and what is left over?" Seventeen meter readings shared over five technicians: each gets 3, and 2 are left.

In general, for a whole number a and a positive whole number n there is exactly one way to write

Here q is the quotient (how many times n fits) and r the remainder. The remainder is written a \bmod n, read "a mod n": 17 \bmod 5 = 2. The condition 0 \le r \lt n is what makes the answer unique; without it you could also write 17 = 2 \cdot 5 + 7.

Python computes both parts at once with divmod, and separately with floor division // and the modulo operator %:

print(17 // 5, 17 % 5)
print(divmod(17, 5))
print(divmod(1440, 60))          # minutes in a day -> (hours, minutes)
print(25 % 5, 3 % 5)             # a multiple gives 0; a smaller number stays

3 2
(3, 2)
(24, 0)
0 3

A remainder of 0 means n divides a exactly; divisors and multiples are the subject of Divisibility, Primes, GCD and LCM.

Clock arithmetic

A clock already does modular arithmetic. A batch job at Kestrel Energy starts at 22:00 and runs for 5 hours. It does not end at 27:00: after 23 the hours start again at 0, and the job ends at 03:00. That is

This is clock arithmetic: counting on a circle with a fixed number of positions, where passing the last position takes you back to the first. The general name is modular arithmetic: arithmetic with whole numbers in which only the remainder after division by a fixed number n, the modulus, counts. Hours use modulus 24, minutes 60, days of the week 7, and the bits of an 8-bit counter 2^{8} = 256.

# A job starts at 22:00 and takes 5 hours
print((22 + 5) % 24)

# A backup starts at 23:50 and takes 25 minutes: count in minutes
end = (23 * 60 + 50 + 25) % (24 * 60)
print(divmod(end, 60))

# Day of the week, 0 = Monday: 100 days after a Monday
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
print(days[(0 + 100) % 7])

3
(0, 15)
Wed

The backup ends at 00:15. Working in the smallest unit (minutes) and converting back at the end avoids handling the hours and minutes separately. And 100 days after a Monday is a Wednesday because 100 = 14 \cdot 7 + 2: fourteen whole weeks bring you back to Monday, and two more days make it Wednesday.

Negative numbers: languages disagree

What is -17 \bmod 5? The mathematical rule 0 \le r \lt 5 gives a clear answer: -17 = -4 \cdot 5 + 3, so the remainder is 3. On a clock that is natural: three hours before 01:00 is 22:00, not "−2 o'clock".

Programming languages, however, define % in two different ways, depending on how they round the quotient:

• Floor (round down): Python, and also Ruby. The quotient is \lfloor -17 / 5 \rfloor = \lfloor -3.4 \rfloor = -4, so r = -17 - (-4)(5) = 3. The remainder has the sign of the divisor.
• Truncate (round toward zero): C (since C99), Java, C# and JavaScript. The quotient is -3, so r = -17 - (-3)(5) = -2. The remainder has the sign of the dividend.

Both satisfy a = q \cdot n + r; they only pick a different q. Python's behavior is shown in detail on Operators and Expressions. The table below lists all four sign combinations, with math.fmod as the C-style counterpart:

# Python's % follows the sign of the divisor; C and Java follow the dividend
import math
for a, b in ((7, 3), (-7, 3), (7, -3), (-7, -3)):
    print(f"{a:>3} % {b:>2} = {a % b:>2}   fmod = {math.fmod(a, b):>4}")

  7 %  3 =  1   fmod =  1.0
 -7 %  3 =  2   fmod = -1.0
  7 % -3 = -2   fmod =  1.0
 -7 % -3 = -1   fmod = -1.0

The same expressions in C and in JavaScript:

#include <stdio.h>

int main(void) {
    printf("%d %d %d\n", -17 % 5, 17 % -5, -17 / 5);
    return 0;
}

-2 2 -3

console.log(-17 % 5, 17 % -5, Math.trunc(-17 / 5));

// A remainder that is always between 0 and n - 1, for positive n
const mod = (a, n) => ((a % n) + n) % n;
console.log(mod(-17, 5), mod(1 - 3, 24));

-2 2 -3
3 22

Congruence and the rules of modular arithmetic

On a 24-hour clock, 3 and 27 land on the same position, and so do 51 and −21. Numbers that leave the same remainder are equivalent for the calculation. This relation is called congruence: two whole numbers are congruent modulo n when they have the same remainder after division by n, or, equivalently, when their difference is a multiple of n:

Read it as "a is congruent to b modulo n exactly when n divides a minus b". For example 38 \equiv 14 \pmod{12}, because 38 - 14 = 24 = 2 \cdot 12: 38 hours after midnight the 12-hour clock shows the same as 14 hours after. Note the difference in notation: a \bmod n is an operation that produces a number, while a \equiv b \pmod{n} is a statement that is true or false.

Reduce early: the rules

The key property of congruence is that it survives addition, subtraction and multiplication. You may replace any number by its remainder at any step:

This is what makes modular arithmetic practical: the numbers you work with never need to grow beyond n^2 (the product of two remainders). Division is the exception; it only works in a special form (the modular inverse), which is covered with the cryptography that relies on it.

Worked example: the last digit of 7¹⁰⁰

7^{100} has 85 digits, but its last digit is easy, because the last digit of a number is its remainder modulo 10.

1. 7^{1} = 7, last digit 7.
2. 7^{2} = 49, last digit 9.
3. 7^{3}: multiply only the last digits, 9 \cdot 7 = 63, last digit 3.
4. 7^{4}: 3 \cdot 7 = 21, last digit 1.
5. Since 7^{4} \equiv 1 \pmod{10}, the pattern 7, 9, 3, 1 repeats every four powers. And 100 = 25 \cdot 4, so 7^{100} = (7^{4})^{25} \equiv 1^{25} = 1 \pmod{10}.

Python's three-argument pow(base, exp, mod) uses the same reduce-early idea and stays fast even for numbers with hundreds of digits:

print(pow(7, 100, 10), 7 ** 100 % 10, len(str(7 ** 100)))
print(pow(3, 4, 7), 3 ** 4 % 7)
print((38 - 14) % 12 == 0)       # 38 is congruent to 14 mod 12
print((123456 * 654321) % 97, ((123456 % 97) * (654321 % 97)) % 97)

1 1 85
4 4
True
55 55

The last line checks the multiplication rule on bigger numbers. Modular exponentiation and the modular inverse are the heart of RSA and Diffie–Hellman; see The Math Behind Cryptography.

Hashing, sharding and round-robin

Whenever a program must spread items over a fixed number of places, % n is the tool. It turns any whole number into one of exactly n slots: 0, 1, \ldots, n - 1.

• Hash tables compute a hash of the key and store the item in bucket hash % size; see Data Structures.
• Sharding spreads database rows over servers the same way: shard hash(customer_id) % 4.
• Round-robin load balancing sends request number i to server i \bmod n; operating systems use the same idea for round-robin scheduling.
• Ring buffers keep the last n log lines or readings in a fixed array, writing item i to position i \bmod n so that new items overwrite the oldest.

Worked example: adding a fifth shard

Kestrel Energy stores meter readings on four database shards, chosen with a CRC-32 checksum of the meter ID modulo 4. Hamid Rahimi, the database administrator, wants to add a fifth shard and asks how many meters would have to move.

import zlib
from collections import Counter

meters = [f"MTR-{n:06d}" for n in range(1000)]
hashes = [zlib.crc32(m.encode()) for m in meters]

on_four = [h % 4 for h in hashes]
on_five = [h % 5 for h in hashes]
print(sorted(Counter(on_four).items()))
moved = sum(1 for a, b in zip(on_four, on_five) if a != b)
print(f"{moved} of {len(meters)} meters change shard")

# Round-robin over 3 portal servers
print([request % 3 for request in range(7)])

[(0, 250), (1, 250), (2, 250), (3, 250)]
801 of 1000 meters change shard
[0, 1, 2, 0, 1, 2, 0]

1. With four shards the hash spreads the meters evenly: 250 each.
2. A meter stays put only if its hash gives the same remainder modulo 4 and modulo 5. That is true for only about one in five hashes.
3. So about four in five meters move: here 801 of 1000. Plain % n sharding is simple, but changing n reshuffles almost everything. That is why large systems use schemes such as consistent hashing, which move only about 1/n of the keys.

Check digits: IBAN and Luhn

A check digit is an extra digit (or pair of digits) computed from the other digits of a number and stored with it, so that typing errors can be detected without looking anything up. The receiver recomputes it; if it does not match, the number is wrong. Account numbers, payment cards, barcodes (EAN) and book numbers (ISBN) all use one, and each check is a remainder calculation.

The Luhn algorithm (payment cards)

The Luhn algorithm, defined in ISO/IEC 7812 for payment card numbers, works modulo 10. Starting from the rightmost digit (the check digit itself), double every second digit; if doubling gives more than 9, subtract 9 (the same as adding its two digits). The number is valid when the sum of all digits is a multiple of 10.

Worked example with the test number 79927398713:

1. Digits from the right: 3, 1, 7, 8, 9, 3, 7, 2, 9, 9, 7.
2. Double the second, fourth, sixth … of them: 1 → 2, 8 → 16 → 7, 3 → 6, 2 → 4, 9 → 18 → 9. Their sum is 2 + 7 + 6 + 4 + 9 = 28.
3. Add the digits that were not doubled: 3 + 7 + 9 + 7 + 9 + 7 = 42.
4. Total 28 + 42 = 70, and 70 \bmod 10 = 0: valid.

def luhn_valid(number):
    total = 0
    for i, ch in enumerate(reversed(number)):
        d = int(ch)
        if i % 2 == 1:          # every second digit from the right
            d *= 2
            if d > 9:
                d -= 9
        total += d
    return total % 10 == 0


print(luhn_valid("79927398713"))
print(luhn_valid("79927398710"))      # last digit mistyped
print(luhn_valid("4111111111111111"))  # a well-known test card number

True
False
True

Luhn catches every single mistyped digit and almost every swap of two neighboring digits; the one swap it misses is 09 ↔ 90, because both pairs add the same amount to the sum.

IBAN: modulo 97

The IBAN (International Bank Account Number, ISO 13616) uses a stronger check, called MOD 97-10 in ISO 7064. The two digits after the country code are chosen so that the whole IBAN, rearranged and read as one big number, leaves remainder 1 when divided by 97. Worked example with the fictional Dutch IBAN NL13 TEST 0123 4567 89 (TEST is not a real bank code):

1. Remove the spaces: NL13TEST0123456789.
2. Move the first four characters to the end: TEST0123456789NL13.
3. Replace each letter by a number, A = 10, B = 11, … Z = 35: T = 29, E = 14, S = 28, N = 23, L = 21. The result is the 24-digit number 291428290123456789232113.
4. Divide by 97: the remainder is 1, so the IBAN is valid.

To create the check digits, do the same with 00 in their place and take 98 - (N \bmod 97), written with two digits. In Python, int(ch, 36) converts a letter to its number, because base 36 uses the digits 0–9 and then A–Z:

def to_digits(text):
    return "".join(str(int(ch, 36)) for ch in text)   # A=10 ... Z=35


def iban_valid(iban):
    s = iban.replace(" ", "").upper()
    s = s[4:] + s[:4]                  # move country + check digits to the end
    return int(to_digits(s)) % 97 == 1


def iban_check_digits(country, bban):
    n = int(to_digits(bban + country + "00"))
    return f"{98 - n % 97:02d}"


print(iban_check_digits("NL", "TEST0123456789"))
print(iban_valid("NL13 TEST 0123 4567 89"))
print(iban_valid("NL13 TEST 0123 4567 98"))   # last two digits swapped

13
True
False

MOD 97 detects every single wrong digit and every swap of two neighboring digits. The security page shows the same check used to recognize account numbers in data loss prevention.

Worked example: mod 97 without big integers

A 24-digit number does not fit in a 64-bit integer (the maximum is about 9.2 \times 10^{18}, 19 digits). Python has unlimited integers, but in C, Java or a spreadsheet you need the reduce-early rule: compute the remainder of the first chunk, put that remainder in front of the next chunk, and repeat.

digits = "291428290123456789232113"
remainder = 0
for i in range(0, len(digits), 9):
    chunk = digits[i:i + 9]
    remainder = int(str(remainder) + chunk) % 97
    print(chunk, "->", remainder)
print(remainder == int(digits) % 97)

291428290 -> 35
123456789 -> 65
232113 -> 1
True

It works because putting a remainder r in front of a chunk of k digits is the number r \cdot 10^{k} + \text{chunk}, which is congruent modulo 97 to the original prefix followed by that chunk. No intermediate value ever has more than 11 digits.