Modular Arithmetic Explained — Binary Exponentiation, Modular Inverse, Fermat's Little Theorem [LC 50, Google, Stripe]

Algorithm Statement#

Modular arithmetic is the system of integers under a fixed modulus m, where every value is reduced to its remainder mod m. The four operations you must master:

1. Binary exponentiation: compute $a^n \bmod m$ in $O(\log n)$.
2. Modular inverse: find $a^{-1} \bmod m$ such that $a \cdot a^{-1} \equiv 1 \pmod{m}$.
3. Modular addition / subtraction / multiplication with overflow safety.
4. Fermat's little theorem: if p is prime and $\gcd(a, p) = 1$, then $a^{p-1} \equiv 1 \pmod{p}$.

Constraints typical in interviews:

• $1 \le n \le 10^{18}$
• $1 \le a, m \le 10^9$
• $m$ is often prime, usually $10^9 + 7$ or $998244353$.

Example (LC 50 Pow(x, n) variant for integers under mod):

Input:  a = 2, n = 10, m = 1000
Output: 24       (since 2^10 = 1024, and 1024 mod 1000 = 24)

Why This Problem Matters#

Almost every hard problem at Google, Meta, Stripe, and competitive programming sites uses modular arithmetic. The reason is simple: counting problems and combinatorial answers explode quickly. The number of paths in a grid, the number of valid sequences, the number of subsets satisfying a constraint — these grow far beyond 64-bit integers. To return a finite answer, problem setters add the phrase "return the answer modulo $10^9 + 7$."

If you cannot do modular exponentiation in $O(\log n)$, problems like LC 50 Pow(x, n), LC 1922 Count Good Numbers, LC 2400 Number of Ways to Reach a Position After Exactly k Steps, and LC 1735 Count Ways to Make Array With Product are unreachable. Stripe specifically uses modular arithmetic in cryptographic verification, idempotency hashing, and fee computation — interviewers there expect candidates to know binary exponentiation cold.

This is the gateway technique. Get it right and the entire number-theory tree opens up.

The Core Insight#

Modular arithmetic obeys the same algebraic identities as ordinary arithmetic, with one big exception: division. The four key identities are:

Subtraction needs the extra $+ m$ because the difference can be negative; many languages return negative remainders for negative operands.

Binary exponentiation rests on the binary expansion of the exponent. Write $n$ in binary as $b_{k} b_{k-1} \dots b_0$. Then

We square $a$ at each step (so we have $a, a^2, a^4, a^8, \dots$) and multiply only when the corresponding bit of $n$ is 1. Total work: $O(\log n)$ multiplications.

Modular inverse via Fermat. If $p$ is prime and $\gcd(a, p) = 1$, Fermat's little theorem says $a^{p-1} \equiv 1 \pmod{p}$. Multiplying both sides by $a^{-1}$ gives $a^{-1} \equiv a^{p-2} \pmod{p}$. So computing $a^{p-2} \bmod p$ via binary exponentiation gives you $a^{-1}$ in $O(\log p)$ time. This works only when $p$ is prime — otherwise use the Extended Euclidean Algorithm.

Proof sketch of Fermat. Consider the residues $a, 2a, 3a, \dots, (p-1)a \bmod p$. Because $\gcd(a, p) = 1$, these are a permutation of $1, 2, \dots, p-1$. Multiplying both sides: $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$. Cancelling $(p-1)!$ (which is invertible mod $p$ by Wilson) yields $a^{p-1} \equiv 1$.

Visual Dry Run#

Compute $3^{13} \bmod 1000$ using binary exponentiation. The exponent in binary is $13 = 1101_2$.

result = 1
base   = 3
exp    = 13 (binary 1101)
 
Step 1: exp & 1 = 1 → result = 1 * 3 = 3
        base = 3*3 = 9, exp = 6 (binary 110)
 
Step 2: exp & 1 = 0 → result unchanged (3)
        base = 9*9 = 81, exp = 3 (binary 11)
 
Step 3: exp & 1 = 1 → result = 3 * 81 = 243
        base = 81*81 = 6561 mod 1000 = 561, exp = 1
 
Step 4: exp & 1 = 1 → result = 243 * 561 mod 1000
        = 136323 mod 1000 = 323
 
Final: 3^13 mod 1000 = 323

Verification: 3^{13} = 1{,}594{,}323, and 1{,}594{,}323 \bmod 1000 = 323. Correct.

For modular inverse, find $7^{-1} \bmod 13$. By Fermat, $7^{-1} \equiv 7^{11} \pmod{13}$. Compute $7^{11} \bmod 13 = 2$. Verify: $7 \cdot 2 = 14 \equiv 1 \pmod{13}$. Correct.

Solution (Optimal)#

Python#

MOD = 10**9 + 7
 
def power(a: int, n: int, m: int = MOD) -> int:
    """Compute a^n mod m in O(log n)."""
    a %= m
    result = 1
    while n > 0:
        if n & 1:
            result = result * a % m
        a = a * a % m
        n >>= 1
    return result
 
def mod_inverse(a: int, p: int = MOD) -> int:
    """Modular inverse of a mod prime p via Fermat's little theorem."""
    return power(a, p - 2, p)
 
def mod_add(a: int, b: int, m: int = MOD) -> int:
    return (a % m + b % m) % m
 
def mod_sub(a: int, b: int, m: int = MOD) -> int:
    return (a % m - b % m + m) % m
 
def mod_mul(a: int, b: int, m: int = MOD) -> int:
    return (a % m) * (b % m) % m
 
def mod_div(a: int, b: int, p: int = MOD) -> int:
    return mod_mul(a, mod_inverse(b, p), p)

JavaScript#

const MOD = 1_000_000_007n;
 
function power(a, n, m = MOD) {
    a = ((a % m) + m) % m;
    let result = 1n;
    while (n > 0n) {
        if (n & 1n) result = (result * a) % m;
        a = (a * a) % m;
        n >>= 1n;
    }
    return result;
}
 
function modInverse(a, p = MOD) {
    return power(a, p - 2n, p);
}
 
function modMul(a, b, m = MOD) {
    return ((a % m) * (b % m)) % m;
}

Complexity: $O(\log n)$ time, $O(1)$ extra space for each operation.

Use BigInt in JavaScript whenever the modulus exceeds $2^{26}$, because the intermediate product $a \cdot b$ can overflow 53-bit Number precision. Python integers are arbitrary precision, so the issue does not arise.

Common Mistakes#

1. Forgetting to reduce inputs. If a is already larger than m, the first multiplication can overflow. Always start with a %= m.
2. Negative remainders in subtraction. Python's % returns non-negative results, but C, C++, Java, and JavaScript do not. Add m before the final mod.
3. Using Fermat with a composite modulus. Fermat requires the modulus to be prime. For composite m, use the Extended Euclidean Algorithm.
4. Computing inverse of zero or a non-coprime value. $0$ has no inverse, and if $\gcd(a, m) \neq 1$ the inverse does not exist.
5. Iterative multiplication instead of fast power. Computing $a^n$ by multiplying $n$ times is $O(n)$ — far too slow for $n = 10^{18}$.
6. JavaScript Number overflow. Native numbers lose precision past $2^{53}$. Always use BigInt for serious modular work.
7. Mutating the global MOD. Keep MOD as a constant, not a variable that can be accidentally reassigned.

Interview Tips#

• State the modulus first: "I will assume MOD = 1e9 + 7 unless told otherwise." Show you know the convention.
• Write the helper power(a, n, m) once and reuse it. Interviewers love clean abstractions.
• When asked for a closed-form on a counting problem, mention modular inverse for division — this signals fluency.
• If the modulus is not prime, immediately pivot to Extended Euclidean. Do not blindly apply Fermat.
• For very large moduli where $a \cdot b$ overflows 64 bits, mention __int128 (C++) or Python's arbitrary precision.

Follow-up Questions#

Q1: How would you compute the inverse if the modulus is not prime? A: Use the Extended Euclidean Algorithm. It returns integers $x, y$ such that $a x + m y = \gcd(a, m)$. If $\gcd(a, m) = 1$, then $x \bmod m$ is the inverse.

Q2: Compute $a^n \bmod m$ where $m$ does not fit in 64 bits. A: Use Python's native big integers, or in C++ use __int128 for the intermediate product, or use Montgomery reduction.

Q3: Compute the sum of $a^0 + a^1 + \dots + a^{n-1} \bmod m$ in $O(\log n)$. A: Use the geometric-sum recurrence: split into even and odd indices and recurse. Or use $\frac{a^n - 1}{a - 1}$ with modular inverse when $a - 1$ is coprime to $m$.

Q4: Why is $10^9 + 7$ chosen as the modulus? A: It is prime (so Fermat works), close to $2^{30}$ (so $a \cdot b$ fits in 64 bits), and unlikely to collide with structural properties of the problem.

Key Takeaways#

• Binary exponentiation computes $a^n \bmod m$ in $O(\log n)$ by repeated squaring on the binary digits of $n$.
• Fermat's little theorem turns modular inverse into modular exponentiation: $a^{-1} \equiv a^{p-2} \pmod{p}$ when $p$ is prime.
• Always reduce intermediates modulo $m$ to prevent overflow; use BigInt in JavaScript and long long (or __int128) in C++.
• Subtraction needs + m then % m in languages where the modulo of a negative is negative.
• Composite moduli demand Extended Euclidean, not Fermat — the prime-only assumption is a common interview trap.
• The modulo $10^9 + 7$ is prime and chosen so that products of two values under it still fit in a 64-bit integer.