SyntaxPilot
Courses/Competitive Programming/Lesson 22

Competitive Programming · Lesson 22 of 90 · 13 min

Modular inverse and Fermat's little theorem

queued

These are the notes for Competitive Programming episode 22 (number theory 4). Episode 21 showed that addition and multiplication survive "print the answer modulo 10^9 + 7", so we can take % M after every step and compute even 2^(10^18) with fast power. Today we hit the one operation that does not survive: division. In an original problem, Prize Split, the obvious power(2, k) / n gets Wrong Answer. A kirana shop calculator with a broken ÷ key leads to the modular inverse (the number that undoes multiplication), searching for it gets Time Limit Exceeded, and Fermat's little theorem turns the inverse into one call: power(n, M - 2), about 30 steps. A million-check stress test confirms it, and three real bugs close the episode. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hooks

The kirana shop's broken ÷ key. A shopkeeper must split ₹1000 among 4 partners, but the ÷ key on his calculator is broken. He types 1000 × 0.25 instead and gets 250: the same answer with no division. It works because 4 × 0.25 = 1: multiplying by 0.25 undoes multiplying by 4. 0.25 is the inverse of 4. Mod world has no decimals, but it can still have undo numbers: modulo 7, 4 · 2 = 8, which leaves remainder 1, so 2 is the inverse of 4 (mod 7).

The seat shuffle. Six students sit in seats 1 to 6. The teacher says: "whoever is in seat k, move to seat 3 · k mod 7". Seat 1 → 3, 2 → 6, 3 → 2, 4 → 5, 5 → 1, 6 → 4. Nobody shares a seat and no seat is left empty: it is only a shuffle. That shuffle is the whole proof of Fermat's little theorem (below).

Recap: what survives mod M

  • Modulo (%): a % M is the remainder when a is divided by M. 17 % 7 = 3.
  • Contest problems whose answers are huge ask for the answer modulo M, usually M = 10^9 + 7 (a prime that fits in an int, and whose square fits in a long long).
  • Addition survives: (a + b) % M == (a % M + b % M) % M.
  • Multiplication survives: (a · b) % M == (a % M) · (b % M) % M.
  • So we can take % M after every single step, and numbers never grow past M. Fast power (binary exponentiation, episode 21) uses this to compute a^b % M in about log₂ b steps:
ll power(ll a, ll b) {          // episode 21: a^b % M
    ll r = 1;
    for (a %= M; b > 0; b >>= 1, a = a * a % M)
        if (b & 1) r = r * a % M;
    return r;
}
  • Division does not survive. That is today's problem.

Problem W · Prize Split

Problem W · Prize Split (written for this course). A quiz team of n friends wins 2^k rupees and splits it equally. For each of q queries (k, n), print one friend's share modulo M = 10^9 + 7. If the share is a fraction P / Q, print P · Q^(-1) mod M (it always exists here).

1 ≤ q ≤ 2·10^5, 1 ≤ k ≤ 10^18, 1 ≤ n ≤ 10^9. Time limit 2 seconds.

Sample input Sample output Why
3
10 4
100 4
3 3
256
494092823
666666674
1024 / 4 = 256 · 2^100 / 4 = 2^98 ≡ 494092823 · 8 / 3 as a fraction mod M
2
1 1
1000000000000000000 1000000000
2
40074821
2 / 1 = 2 · the largest k and n

(The phrase "print P · Q^(-1) mod M" is explained below: it is exactly the modular inverse.)

The obvious attempt: divide after the mod (Wrong Answer)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll M = 1000000007;

ll power(ll a, ll b) {          // episode 21: a^b % M
    ll r = 1;
    for (a %= M; b > 0; b >>= 1, a = a * a % M)
        if (b & 1) r = r * a % M;
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        ll k, n;
        cin >> k >> n;
        cout << power(2, k) / n << "\n";
    }
    return 0;
}
Input Output Expected
10 4 256 256 ✓
100 4 244092821 494092823 ✗
3 3 2 666666674 ✗

Why division breaks

Take a tiny modulus, 7:

  • 12 / 4 = 3 (the true answer).
  • 12 % 7 = 5, and 5 / 4 = 1 in integer division. Wrong.

Taking % 7 threw away a 7. The remainder 5 is not a multiple of 4 any more, so dividing it means nothing. Exactly the same happened to 2^100: 2^100 % M = 976371285, and 976371285 / 4 = 244092821 (rounded down), which has nothing to do with 2^98 % M.

And we cannot skip the mod: 2^(10^18) has about 3·10^17 digits. No computer can store it.

The modular inverse

The modular inverse of n (mod M), written n^(-1), is the number x in 1 … M − 1 with

n · x % M == 1

Dividing by n = multiplying by n^(-1). Check on the example that broke: 12 % 7 = 5; the inverse of 4 mod 7 is 2 (4 · 2 = 8 ≡ 1); 5 · 2 = 10, and 10 % 7 = 3. The right answer, from the remainder alone.

When does it exist? Only when n and M share no common factor, i.e. gcd(n, M) = 1 (episode 19). Mod 6, 2 has no inverse: 2 · x is always even, so 2 · x % 6 is 0, 2 or 4, never 1. That is why contests choose a prime M: then every n that is not a multiple of M has an inverse. If n can be a multiple of M, there is no inverse at all, just like dividing by zero.

Fractions mod M. 8 / 3 is not a whole number, so "8 / 3 mod M" means 8 · 3^(-1) mod M. 3^(-1) = 333333336 (3 · 333333336 = 1000000008 ≡ 1), so 8 / 3 ≡ 8 · 333333336 % M = 666666674. Check: 3 · 666666674 = 2000000022, and 2000000022 % M = 8. This is what "print P · Q^(-1) mod M" means, and you will see that sentence in hundreds of problems (probabilities, expected values, averages).

n n^(-1) mod 10^9 + 7 check
2 500000004 2 · 500000004 = 1000000008 ≡ 1
3 333333336 3 · 333333336 = 1000000008 ≡ 1
4 250000002 4 · 250000002 = 1000000008 ≡ 1
10 700000005 10 · 700000005 = 7000000050 ≡ 1

Brute force: search for the inverse (Time Limit Exceeded)

ll inverse(ll n) {              // try x = 1, 2, 3 ...
    for (ll x = 1; x < M; x++)
        if (n % M * x % M == 1) return x;
    return -1;
}
// in main:  cout << power(2, k) * inverse(n) % M << "\n";

On the sample it prints the right answers, 256, 494092823, 666666674, but it already needs about a second: the inverse of 4 is 250000002, a quarter of a billion tries away. On a worst case of 2·10^5 queries with n near 10^9 (built inside main):

int main() {
    int q = 200000;                 // worst case, built here
    ll total = 0;
    while (q--) {
        ll n = 1000000000 - q;
        total = (total + inverse(n)) % M;
    }
    cout << total << "\n";
    return 0;
}

Result: Time Limit Exceeded (still running after 8 seconds). Each search can take up to M ≈ 10^9 steps; 2·10^5 of them is about 2·10^14.

Fermat's little theorem

Look for a pattern. Modulo 7, keep multiplying:

a a^1 a^2 a^3 a^4 a^5 a^6
3 3 2 6 4 5 1
2 2 4 1 2 4 1

Every a from 1 to 6 gives a^6 ≡ 1 (mod 7), and 6 = 7 − 1. This is Fermat's little theorem (Pierre de Fermat, around 1640):

If p is prime and a is not a multiple of p, then a^(p−1) ≡ 1 (mod p).

Peel one a off: a · a^(p−2) ≡ 1. So

a^(-1) ≡ a^(p−2) (mod p), and in code inverse(n) = power(n, M - 2).

For 3 mod 7: 3^5 = 243 = 7 · 34 + 5, so 3^(-1) = 5, and 3 · 5 = 15 ≡ 1 ✓.

M − 2 is about 10^9, but fast power needs only about 30 squarings to get there: O(log M).

Why it works: the seat shuffle

Take p = 7, a = 3, and multiply each of 1 … 6 by 3, mod 7:

k 1 2 3 4 5 6
3 · k mod 7 3 6 2 5 1 4

The second row is the same six numbers, shuffled. (Two seats can't collide: if 3i ≡ 3j then 7 divides 3(i − j), and since 7 is prime and doesn't divide 3, it divides i − j, so i = j.) So the products of the two rows are equal mod 7:

3^6 · (1 · 2 · … · 6) ≡ 1 · 2 · … · 6 (mod 7)

1 · 2 · … · 6 has no factor 7, so it has an inverse and we can cancel it: 3^6 ≡ 1. The same argument works for any prime p and any a not divisible by p. It also shows why p must be prime: with a non-prime modulus, some seats can collide.

The accepted solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll M = 1000000007;

ll power(ll a, ll b) {          // episode 21: a^b % M
    ll r = 1;
    for (a %= M; b > 0; b >>= 1, a = a * a % M)
        if (b & 1) r = r * a % M;
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        ll k, n;
        cin >> k >> n;
        cout << power(2, k) * power(n, M - 2) % M << "\n";
    }
    return 0;
}
Input Output
3 / 10 4 / 100 4 / 3 3 256 / 494092823 / 666666674
2 / 1 1 / 1000000000000000000 1000000000 2 / 40074821
2·10^5 random queries about 0.2 s

power(2, k) * power(n, M - 2) multiplies two numbers below M ≈ 10^9: at most about 10^18, which fits in a long long (max ≈ 9.2·10^18). Then % M brings it back down.

A million-check stress test

A stress test checks a solution against something we trust, on many random inputs. Here the trusted fact is the definition itself: n · n^(-1) % M must be 1.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll M = 1000000007;

ll power(ll a, ll b) {          // episode 21: a^b % M
    ll r = 1;
    for (a %= M; b > 0; b >>= 1, a = a * a % M)
        if (b & 1) r = r * a % M;
    return r;
}

int main() {
    mt19937 rng(22);
    int ok = 0;
    for (int t = 0; t < 1000000; t++) {
        ll n = rng() % (M - 1) + 1;     // 1 .. M-1
        if (n * power(n, M - 2) % M == 1) ok++;
    }
    cout << ok << " / 1000000 checks passed\n";
    return 0;
}

Output: 1000000 / 1000000 checks passed (about 0.15 s). mt19937 is C++'s fast Mersenne Twister random number generator; the seed 22 makes every run produce the same numbers, so a failure can be reproduced.

Bonus: all inverses 1 … n in O(n)

When you need the inverse of every number from 1 to n (n up to 10^7), there is a linear-time recurrence. Write M = (M / i) · i + (M % i). Mod M the left side is 0, so (M / i) · i ≡ −(M % i). Multiply both sides by i^(-1) · (M % i)^(-1):

i^(-1) ≡ −(M / i) · (M % i)^(-1) (mod M)

M % i < i, so (M % i)^(-1) is already in the table:

vector<ll> inv(n + 1);
inv[1] = 1;
for (int i = 2; i <= n; i++)
    inv[i] = (M - M / i) * inv[M % i] % M;

Checked against power(i, M - 2) for every i ≤ 10^6: 0 mismatches (inv[2] = 500000004, inv[10] = 700000005). For n = 10^7 it took about 0.45 s on our test machine, against about 2.2 s for 10^7 separate Fermat calls. Episode 23 uses a related trick for the inverses of factorials.

Complexity vs the constraints

Approach Time per query Worst case here (q = 2·10^5) Verdict
power(2, k) / n O(log k) fast Wrong Answer
Search x = 1, 2, … O(M) up to 2·10^5 · 10^9 = 2·10^14 TLE
Fermat: power(n, M - 2) O(log k + log M) ≈ 60 + 30 ≈ 2·10^7 steps Accepted, ≈ 0.2 s
Inverse table 1 … n O(1) after O(n) build n ≤ 10^7 when you need all of them

Common mistakes (and the real outputs)

Bug 1: int inside the power function

int power(int a, int b) {          // episode 21: a^b % M
    int r = 1;
    for (a %= M; b > 0; b >>= 1, a = a * a % M)
        if (b & 1) r = r * a % M;
    return r;
}

On the sample the program prints 0, 0, 381855169 instead of 256, 494092823, 666666674, with no error message. a · a can be close to 10^18, but an int holds at most 2147483647: the product overflows (wraps around; in C++ signed overflow is even undefined behaviour) before % M runs. Fix: long long for every value that gets multiplied.

Bug 2: a modulus that isn't prime

const ll M = 1000000000;           // typo: 10^9, not 10^9 + 7

The stress test prints 0 / 1000000 checks passed. 10^9 = 2^9 · 5^9 is not prime, so Fermat's theorem does not apply, and even numbers (and multiples of 5) have no inverse at all. Fix: const ll M = 1000000007; (or the other common contest prime, 998244353). Copy the modulus from the statement; never retype it.

Bug 3: forgetting the last % M

        cout << power(2, k) * power(n, M - 2) << "\n";

Output: 256000002048, 244092823202742570, 2666666688. The first is 256 + 256 · M: the right remainder, never reduced. The judge compares text, so this is Wrong Answer. Fix: % M after every multiplication.

Summary table

Mistake What you see Why Fix
power(2, k) / n 244092821 (expected 494092823) % threw away multiples of M * power(n, M - 2) % M
int power(int a, int b) 0 0 381855169, no error a · a overflows int long long everywhere
const ll M = 1000000000; 0 / 1000000 checks passed 10^9 is not prime M = 1000000007
x * power(n, M - 2) with no % M 256000002048 (expected 256) product never reduced % M after every ×
inverse of a multiple of M power(M, M - 2) returns 0, silently no inverse exists (like ÷ 0) check the constraints
searching x = 1, 2, … Time Limit Exceeded up to 10^9 tries per query Fermat

Mini project

Build a reusable Mint (modular integer) helper: a struct holding a value in 0 … M − 1 with +, −, · (all reducing mod M, with the negative fix from episode 21), pow(b), inv() (Fermat) and / (multiply by inv()). Stress-test it: for a million random pairs (a, b) with b ≠ 0, check that (a / b) * b == a, and that a.inv().inv() == a. Then rewrite Problem W in three lines using it.

Practice

These follow the video's homework.

  1. Print the average of n numbers (each ≤ 10^9) modulo 10^9 + 7.

    Answer Average = (sum) / n = (sum % M) · power(n, M − 2) % M. The sum can be reduced as you add. Results from running it: <code>1 2 4</code> → 7 / 3 → <code>333333338</code>; <code>5 10</code> → 15 / 2 → <code>500000011</code> (= 7 + 2^(-1), since 7.5 = 7 + 1/2).

  2. Compute the inverses of all numbers 1 … n (n ≤ 10^7) in O(n).

    Answer The recurrence from the bonus section: <code>inv[1] = 1; inv[i] = (M - M / i) * inv[M % i] % M</code>. Checked against Fermat for every i ≤ 10^6 (0 mismatches). <code>inv[2] = 500000004</code>, <code>inv[10] = 700000005</code>.

  3. Print 1 + 2 + … + n modulo M, for n ≤ 10^18.

    Answer The formula n(n + 1) / 2, with division by 2 done as multiplication by 2^(-1) = 500000004: <code>n % M * ((n + 1) % M) % M * 500000004 % M</code>. Reduce n first, or n · (n + 1) overflows. n = 10 → <code>55</code>; n = 10^18 → <code>1225</code> (because 10^18 ≡ 49 mod M, and 49 · 50 / 2 = 1225).

  4. The expected value of one roll of a fair six-sided die, as a fraction mod M.

    Answer (1 + 2 + 3 + 4 + 5 + 6) / 6 = 21 / 6 = 7 / 2. Both give the same residue: 21 · 6^(-1) ≡ 7 · 2^(-1) ≡ <code>500000007</code>. (A fraction has one value mod M, however you write it.)

  5. Without code: what is the inverse of 10 modulo 7? And why does 6 have no inverse modulo 9?

    Answer 10 ≡ 3 (mod 7), and 3 · 5 = 15 ≡ 1, so 10^(-1) ≡ 5 (Fermat agrees: 10^5 % 7 = 5). 6 and 9 share the factor 3, so 6 · x is always a multiple of 3 and can never leave remainder 1 mod 9.

Quick quiz

11 is prime. What is power(3, 11 - 2), i.e. 3^9 % 11?

A) 1 · B) 4 · C) 3 · D) 9

Answer

B. By Fermat, 3^9 is the inverse of 3 mod 11, and 3 · 4 = 12 ≡ 1. Directly: 3^9 = 19683 = 11 · 1789 + 4. A would be 3^10 (= 3^(p−1)).

Interview questions

  1. Why can't you divide remainders directly? Taking % M throws away multiples of M, so the remainder need not be divisible by n any more: 12 / 4 = 3 but (12 % 7) / 4 = 1.
  2. What is a modular inverse, and when does it exist? The x with n · x ≡ 1 (mod M); it exists exactly when gcd(n, M) = 1.
  3. State Fermat's little theorem and how it gives the inverse. For prime p and a not divisible by p, a^(p−1) ≡ 1 (mod p); so a^(p−2) is a's inverse, computed with fast power in O(log p).
  4. Why do contests use 10^9 + 7? It is prime (so every non-multiple has an inverse), fits in a 32-bit int, and the product of two residues (< 1.0·10^18) fits in a 64-bit long long.
  5. What if the modulus is not prime? Fermat fails. Use the extended Euclidean algorithm (episode 25), which finds the inverse whenever gcd(n, M) = 1, or Euler's theorem (episode 27).
  6. How do you compute many inverses quickly? The O(n) recurrence inv[i] = (M - M / i) * inv[M % i] % M, or (for factorials) one Fermat call plus a backward pass (episode 23).

Glossary

Term Meaning Example
Modulo (%) The remainder after division 17 % 7 = 3
M = 10^9 + 7 The usual contest modulus, a prime const ll M = 1000000007;
Congruent (≡) Same remainder mod M 8 ≡ 1 (mod 7)
Fast power (binary exponentiation) a^b % M in O(log b) by repeated squaring power(2, 100) in 7 squarings
Modular inverse (n^(-1)) The x with n · x ≡ 1 (mod M) 4^(-1) ≡ 2 (mod 7)
Modular division Multiply by the inverse instead of dividing 12 / 4 ≡ 5 · 2 ≡ 3 (mod 7)
gcd Greatest common divisor (episode 19) gcd(6, 9) = 3, so 6 has no inverse mod 9
Prime A number with exactly two divisors 7, 11, 10^9 + 7
Fermat's little theorem p prime, p ∤ a ⇒ a^(p−1) ≡ 1 (mod p) 3^6 ≡ 1 (mod 7)
P · Q^(-1) mod M How a fraction P / Q is printed in contests 8 / 3 → 666666674
Integer overflow A value too big for its type wraps around a · a in an int
Undefined behaviour C++ makes no promise what happens (e.g. signed overflow) 0 0 381855169
Stress test Check a solution on many random inputs against something trusted 1000000 / 1000000 checks passed
mt19937 C++'s Mersenne Twister random generator mt19937 rng(22);
Seed The starting value of a random generator; same seed, same numbers 22
Inverse table All inverses 1 … n in O(n) inv[i] = (M - M / i) * inv[M % i] % M

Summary

  • + and × survive % M; division does not: (a % M) / n gives Wrong Answer (244092821 instead of 494092823).
  • Dividing by n is multiplying by its modular inverse, the x with n · x ≡ 1. It exists when gcd(n, M) = 1; for a prime M, whenever n isn't a multiple of M.
  • Searching for x one by one is O(M) per query: TLE.
  • Fermat's little theorem: a^(p−1) ≡ 1 mod a prime p, so inverse(n) = power(n, M - 2), O(log M), about 30 steps. Proof: multiplying 1 … p − 1 by a only shuffles them.
  • Fractions are printed as P · Q^(-1) mod M (8 / 3 → 666666674).
  • Real bugs: int in power (0 0 381855169), a non-prime M (0 / 1000000 checks passed), a missing final % M (256000002048).

Solutions in C++, Java and Python

Problem W · Prize Split

C++: the accepted program above.

Java (tested: the sample gives 256, 494092823, 666666674; the edge input gives 2, 40074821; 2·10^5 random queries gave output identical to C++ in about 0.6 s). BufferedReader and one StringBuilder keep the I/O fast.

import java.io.*;
import java.util.*;

public class Main {
    static final long M = 1_000_000_007L;

    static long power(long a, long b) {        // a^b % M
        long r = 1;
        for (a %= M; b > 0; b >>= 1, a = a * a % M)
            if ((b & 1) == 1) r = r * a % M;
        return r;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long k = Long.parseLong(st.nextToken());
            long n = Long.parseLong(st.nextToken());
            sb.append(power(2, k) * power(n, M - 2) % M).append('\n');
        }
        System.out.print(sb);
    }
}

Python (tested on the same inputs, same outputs; 2·10^5 random queries in about 1.4 s). Python's built-in three-argument pow(base, exp, mod) is fast power, and Python integers never overflow. Since Python 3.8, pow(n, -1, M) also returns the inverse directly.

import sys

M = 10**9 + 7

def main():
    data = sys.stdin.buffer.read().split()
    q = int(data[0])
    out = []
    for i in range(q):
        k, n = int(data[1 + 2 * i]), int(data[2 + 2 * i])
        # pow(base, exp, mod) is Python's built-in fast power
        out.append(pow(2, k, M) * pow(n, M - 2, M) % M)
    print("\n".join(map(str, out)))

main()