Modular ArithmeticModular arithmetic

01Why it exists

Reach for it when you see:The answer is huge and must be reported mod 10⁹+7, intermediate values would overflow, the remainder of a big integer, division under a modulus (fractions, probabilities, expected values), a^b mod m with a huge exponent, modular inverses, cryptography and check digits.

02The core idea

a mod m is the remainder of a divided by m, and a ≡ b (mod m) says a and b leave the same remainder — equivalently, that m divides a − b. The property that makes modular arithmetic useful is that it distributes over addition, subtraction and multiplication: (a + b) mod m = ((a mod m) + (b mod m)) mod m, and likewise for the other two. So you can reduce after every single operation, and intermediate values never reach m. The modulus problems usually pick, 10⁹+7, is prime, and two values below it still sum inside a signed 32-bit integer and multiply to at most 10¹⁸, which a 64-bit integer holds.

Subtraction and division need care. In C++ the % operator keeps the sign of the dividend, so (3 − 5) % 7 is −2 and you have to write (a − b + m) % m to land back in 0 to m − 1. Python's % is never negative. Division does not distribute: (12 / 4) mod 5 = 3, but 12 mod 5 = 2 and 4 mod 5 = 4, and 2 divided by 4 is not even an integer. The fix is the modular inverse: if b · x ≡ 1 (mod m), then x is written b⁻¹, and "divide by b" becomes "multiply by b⁻¹". An inverse exists exactly when gcd(b, m) = 1.

When the modulus is a prime p there is a ready-made formula. Fermat's little theorem says that if a is not a multiple of p, then a^(p−1) ≡ 1 (mod p). The proof is the observation in the demo: multiply each of 1 through p − 1 by a and the remainders are precisely 1 through p − 1 rearranged, so multiplying both sides together and cancelling (p−1)! gives the theorem. Peel off one factor of a and you get a⁻¹ ≡ a^(p−2), computable by fast exponentiation in O(log p) time and O(1) space. For a composite modulus, use the extended Euclidean algorithm instead — also O(log m), and again only when gcd(a, m) = 1. If you need every inverse from 1 to n, the recurrence inv[i] = (p − ⌊p/i⌋) · inv[p mod i] mod p brings the total down to O(n).

Common traps: multiplying first and reducing afterwards, by which point the int has already overflowed — cast to 64 bits before the multiplication; forgetting to add m back after a subtraction; applying Fermat's little theorem to a composite modulus, where the demo's 5^10 mod 12 comes out as 1 while the real inverse is 5; asking for the inverse of 0 or of a multiple of p; and comparing magnitudes after reducing, which does not preserve order. Exponents are another easy slip: the exponent in a^e mod p may be reduced mod p − 1 (provided a is not a multiple of p), never mod p. As for the neighbouring lessons: Fast Exponentiation supplies the method for a^e mod m; the extended Euclidean algorithm from GCD handles non-prime moduli; and the next lesson, Combinatorics, computes C(n, k) mod p by using inverses to turn the division in the factorial formula into multiplication.

03The algorithm

1. 1Fix a modulus m and reduce immediately after every addition, subtraction and multiplication, so intermediate values stay below m. Before multiplying, check that (m − 1)² fits in the integer type you are using.
2. 2Write subtraction as (a − b + m) mod m, and pull any value that might be negative back into 0 to m − 1 with ((x mod m) + m) mod m.
3. 3When you need to divide by b: first confirm gcd(b, m) = 1, then replace "divide by b" with "multiply by the inverse of b".
4. 4For a prime modulus p, the inverse is b^(p−2) mod p, computed by fast exponentiation. For a composite modulus, use the extended Euclidean algorithm.
5. 5When you need every inverse from 1 to n, work upward with inv[i] = (p − ⌊p/i⌋) · inv[p mod i] mod p and finish in O(n).

04Interactive demo

Finding the inverse of 5 modulo 13. The first stage multiplies k = 1 through 12 by 5 and takes the remainder: blue is the current step, and the green row below marks the remainders seen so far. At k = 8 the remainder is 1, and yellow marks 8 as the inverse of 5. After all 12 multiplications each remainder has appeared exactly once, which is the observation Fermat's little theorem rests on, giving 5⁻¹ ≡ 5¹¹. The second stage computes 5¹¹ mod 13 by fast exponentiation: 11 is 1011 in binary, and the table follows base and result bit by bit until result = 8 after four rounds, matching what the search found; that value then gives 7 / 5 ≡ 4. The last stage switches to the composite modulus 12: with a = 4 the remainders are only 0, 4 and 8, so 1 never appears and no inverse exists; with a = 5 an inverse does exist (it is 5), but applying Fermat's formula blindly returns 1, and the yellow outline marks that error.

05Code

Python covers fast exponentiation, inverses via Fermat's little theorem, all inverses from 1 to n in O(n), and the IBAN check that reduces as it reads. C++ covers fast exponentiation plus both the Fermat and extended-Euclid inverses, and demonstrates three situations you will meet: reporting a probability as a fraction under the modulus, the remainder of a negative number, and reducing an exponent mod p − 1.

MOD = 1_000_000_007


def mod_pow(a, e, m=MOD):
    """Fast exponentiation: a^e mod m in O(log e). Python's built-in pow(a, e, m) does the same thing."""
    a %= m
    result = 1 % m
    while e:
        if e & 1:
            result = result * a % m
        a = a * a % m                           # reduce at every step so the numbers never grow
        e >>= 1
    return result


def mod_inv(a, p=MOD):
    """Fermat's little theorem: for prime p the inverse of a is a^(p-2). Multiples of p have no inverse."""
    if a % p == 0:
        raise ValueError("a is a multiple of p, so it has no inverse")
    return mod_pow(a, p - 2, p)


def inverses_upto(n, p=MOD):
    """Every inverse from 1 to n in one O(n) pass. p must be a prime larger than n."""
    inv = [0] * (n + 1)
    if n >= 1:
        inv[1] = 1
    for i in range(2, n + 1):
        inv[i] = (p - p // i) * inv[p % i] % p  # rearranged from p = (p // i)·i + p % i, reduced mod p
    return inv


def iban_valid(iban):
    """IBAN check digits: move the first four characters to the end, map letters to 10 through 35, and the whole number mod 97 must equal 1.
    It runs to thirty-odd digits, so reducing as you read avoids ever building the big integer"""
    s = iban.replace(" ", "")
    s = s[4:] + s[:4]
    r = 0
    for ch in s:
        v = int(ch, 36)                         # 0-9 → 0 through 9, A-Z → 10 through 35
        r = (r * (100 if v >= 10 else 10) + v) % 97
    return r == 1


if __name__ == "__main__":
    print(mod_pow(5, 11, 13), mod_inv(5, 13))   # 8 8
    print(7 * mod_inv(5, 13) % 13)              # 4: this is 7 / 5 modulo 13
    print(mod_inv(2), 2 * mod_inv(2) % MOD)     # 500000004 1
    print(inverses_upto(12, 13)[1:])            # [1, 7, 9, 10, 8, 11, 2, 5, 3, 4, 6, 12]
    print(iban_valid("GB82 WEST 1234 5698 7654 32"), iban_valid("GB82 WEST 1234 5698 7654 23"))   # True False
    print((3 - 5) % 7)                          # 5: Python's % is never negative

06Practice

• LeetCode 1497Check If Array Pairs Are Divisible by k (pull negative remainders back into range first)Medium
• LeetCode 1015Smallest Integer Divisible by K (track the remainder, never the whole number)Medium
• LeetCode 2550Count Collisions of Monkeys on a Polygon (2ⁿ − 2 under a modulus; add it back after subtracting)Medium
• LeetCode 2961Double Modular ExponentiationMedium
• LeetCode 1808Maximize Number of Nice Divisors (split into powers of 3, then fast exponentiation)Hard
• LeetCode 1622Fancy Sequence (undoing a global multiply needs a modular inverse)Hard