Modular Arithmetic & Fast Modular Exponentiation

Modular arithmetic is arithmetic that “wraps around” after reaching a fixed value, the modulus — like a clock wrapping past 12. In DSA it lets you keep numbers small (so they never overflow) while preserving the answer, which is why so many problems ask for a result modulo 1,000,000,007 (1e9 + 7). This page covers the mod properties, the language traps with negative numbers, and fast modular exponentiation in O(log n).

The core properties

Modulo distributes over addition and multiplication, so you can take the mod at every step instead of only at the end:

• (a + b) % m == ((a % m) + (b % m)) % m
• (a * b) % m == ((a % m) * (b % m)) % m
• (a - b) % m == ((a % m) - (b % m) + m) % m ← the + m keeps it non-negative

Subtraction needs the + m because the difference can go negative. The product property is why you cast to a wider type before multiplying: (a % m) * (b % m) can still be up to (m-1)^2, which overflows 32-bit when m ≈ 1e9.

const long long M = 1000000007LL;
long long addMod(long long a, long long b) { return (a + b) % M; }
long long mulMod(long long a, long long b) { return (a % M) * (b % M) % M; }
long long subMod(long long a, long long b) { return ((a - b) % M + M) % M; }

final long M = 1000000007L;
long addMod(long a, long b) { return (a + b) % M; }
long mulMod(long a, long b) { return (a % M) * (b % M) % M; }
long subMod(long a, long b) { return ((a - b) % M + M) % M; }

const M = 1000000007n; // BigInt: safe for the (m-1)^2 product
const addMod = (a, b) => (a + b) % M;
const mulMod = (a, b) => (a % M) * (b % M) % M;
const subMod = (a, b) => ((a - b) % M + M) % M;

M = 1000000007
def add_mod(a, b): return (a + b) % M
def mul_mod(a, b): return a * b % M          # Python ints never overflow
def sub_mod(a, b): return (a - b) % M        # Python % is already non-negative

Language note: The sign of % differs by language. In C++, Java, and JavaScript, -7 % 3 == -1 (sign follows the dividend). In Python, -7 % 3 == 2 (sign follows the divisor), so Python’s mod is already non-negative — you can drop the + m fix. In JavaScript, plain number multiplication loses precision past 2^53, so use BigInt for modular multiplication when m ≈ 1e9.

Why modulo 1e9+7?

It’s a large prime that fits comfortably in a 32-bit signed int, and the product of two values below it fits in 64 bits. Being prime also means every nonzero value has a modular inverse (its “reciprocal” under mod), which you need for modular division — computed via Fermat’s little theorem with the fast-power routine below.

Fast modular exponentiation

Computing base^exp % m by multiplying exp times is O(exp) — far too slow when exp is large. Binary exponentiation squares the base and halves the exponent, doing it in O(log exp). The idea: base^13 = base^8 · base^4 · base^1, reading the exponent’s bits.

long long powMod(long long base, long long exp, long long mod) {
    long long result = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long powMod(long base, long exp, long mod) {
    long result = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

function powMod(base, exp, mod) {
  base = BigInt(base) % BigInt(mod);
  exp = BigInt(exp);
  mod = BigInt(mod);
  let result = 1n % mod;
  while (exp > 0n) {
    if (exp & 1n) result = result * base % mod;
    base = base * base % mod;
    exp >>= 1n;
  }
  return result;
}

def pow_mod(base, exp, mod):
    result = 1 % mod
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

Going deeper: Python has this built in as pow(base, exp, mod), and Java offers BigInteger.modPow. Both use the same O(log exp) algorithm — but interviewers expect you to be able to write it from scratch.

Modular inverse via Fermat’s little theorem

When m is prime and a is not a multiple of m, the modular inverse of a is a^(m-2) % m. This lets you “divide” under a modulus: (x / a) % m == x * inverse(a) % m.

long long inverse(long long a, long long mod) {
    return powMod(a, mod - 2, mod); // mod must be prime
}

long inverse(long a, long mod) {
    return powMod(a, mod - 2, mod); // mod must be prime
}

function inverse(a, mod) {
  return powMod(a, BigInt(mod) - 2n, mod); // mod must be prime
}

def inverse(a, mod):
    return pow(a, mod - 2, mod)  # mod must be prime

Complexity

When you’ll use it

Counting problems that ask for a huge result modulo a prime, polynomial/string hashing, combinatorics (factorials and inverses), and anywhere overflow would otherwise strike. It builds on primes and pairs with the bit-reading trick you’ll see in bit manipulation basics. Next: bit manipulation basics.