Modular arithmetic

Modular arithmetic is arithmetic with remainders. It keeps numbers small however long a calculation runs, and it is behind hash tables, check digits, random number generators and the “answer modulo 1,000,000,007” of many problems. This lesson gives its rules and shows why they are safe to use.

Arithmetic on a clock

Fix a whole number m above 1, called the modulus. The remainder after dividing by m is always one of 0, 1, …, m − 1, so the remainders go round like the hours on a clock with m places: after m − 1 comes 0 again. “a modulo m” means the remainder of a after dividing by m, which Python writes a % m.

Two numbers with the same remainder sit at the same place on the clock. We write

and read it “a is congruent to b modulo m”. So 9 ≡ 2 (mod 7), and 24 ≡ 0 (mod 12). Negative numbers are on the clock too:−3 ≡ 4 (mod 7), because −3 − 4 = −7 is a multiple of 7.

In Python, a % m is always between 0 and m − 1 when m is above 0, even for negative a: -3 % 7 is 4. In C, Java and JavaScript, -3 % 7 is −3, and code in those languages writes ((a % m) + m) % m to get 4.

Take the remainder at every step

Adding, subtracting and multiplying give the same remainder whether you take remainders before or after:

Why? Write a = q · m + r and b = p · m + s, where r and s are the remainders. Then a + b = (q + p) · m + (r + s), so a + b and r + s differ by a multiple of m and have the same remainder. For the product, a · b = (q · p · m + q · s + p · r) · m + r · s, which is r · s plus a multiple of m. Subtraction works like addition.

So a long calculation can take % m after every step, and every number in it stays below m (below m² just before a reduction). The final remainder is the same as if you had worked with the full numbers and taken the remainder at the end:

def factorial_mod(n, m):
    result = 1
    for i in range(2, n + 1):
        result = result * i % m    # stays below m
    return result

factorial_mod(100_000, 1_000_000_007)

Two things do not work this way.

• Division. 6 / 2 = 3, but modulo 4, 6 is 2, and 2 / 2 = 1, which is not 3. Dividing needs an inverse, and not every number has one (lesson 5).
• Exponents. You may reduce the base of a power, but not the exponent: 2⁵ = 32 leaves 2 modulo 3. Reducing the exponent 5 modulo 3 gives 2, and 2² = 4 leaves 1, a different answer. (For a prime modulus there is a rule for exponents: lesson 5.)

Why reduce in Python

Python’s whole numbers never overflow, so why reduce at all? Because huge numbers are slow. 100,000! (the product 1 · 2 · … · 100,000) has 456,574 digits, and each multiplication of such a number costs time in proportion to its length. On a laptop the loop above takes about 0.01 seconds with % m after each step, and over 2 seconds without it. The longer the loop, the bigger the gap.

In C, Java and other languages with 64-bit numbers, reducing is not optional: the product of two remainders must fit in 64 bits. That is why problems so often use m = 1,000,000,007. It is below 2³⁰ (2 to the power 30), so the product of two remainders is below 2⁶⁰ and fits easily. It is also a prime, which lesson 5 needs for division. 998,244,353 is another common prime modulus.

Counting by remainder

The numbers with the same remainder form a class: modulo 3, the classes are {…, 0, 3, 6, …}, {…, 1, 4, 7, …} and {…, 2, 5, 8, …}. For questions about sums and products modulo m, all the numbers in a class behave the same, so you only need to know how many numbers fall in each class.

For example, a + b is a multiple of k exactly when (a % k + b % k) % k == 0: the remainders add up to 0 or to k. So a number with remainder r pairs with the numbers of remainder (k - r) % k. Remainder 0 pairs with itself, and so does k / 2 when k is even. Counting the numbers in each class, instead of looking at every pair, is MATH-P2.

Where remainders are used

• Hash tables put a key in bucket hash(key) % m (HASH-1), and good hash functions are built from multiplying and adding modulo a prime (HASH-4).
• Check digits catch typing mistakes. An ISBN-10 is valid when a weighted sum of its digits is a multiple of 11; bank card numbers use the Luhn rule, with a multiple of 10.
• Repeating things: the day of the week n days from now is (today + n) % 7; a ring buffer moves to (i + 1) % size (STAQ-4).
• Random number generators. A linear congruential generator makes each number from the last as (a * x + c) % m. MATH-P7’s tests use one so that their “random” choices are the same every time.

Now try MATH-P2, Pairs that add to a multiple.