Modular Inverse (Fermat's Little Theorem)

Concept

The modular inverse of a modulo p is the value x such that (a * x) % p = 1. By Fermat's little theorem, if p is prime, then a^(p-1) = 1 (mod p), so a^(p-2) is the modular inverse of a. Compute it using binary exponentiation. This enables modular division: a/b mod p = a * b^(p-2) mod p.

When to Use

  • ▸Computing nCr (combinations) modulo a prime
  • ▸Dividing under modular arithmetic
  • ▸Distributing Apples, counting permutations/combinations mod p
  • ▸Any problem requiring division in modular arithmetic

Intuition

Division doesn't directly work in modular arithmetic. But multiplying by the inverse does. Fermat's little theorem tells us that a^(p-1) = 1 mod p for prime p. So a * a^(p-2) = 1 mod p, meaning a^(p-2) acts as '1/a' in mod world. To compute nCr mod p: calculate n! * inverse(r!) * inverse((n-r)!) mod p, where each inverse is computed via binary exponentiation.

Complexity

Time
O(n + log p) for factorial + inverse
Space
O(n) for factorial table

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

using ll = long long int;
const ll mod = 1e9+7;

ll fact(ll x){
    ll ans = 1;
    for(ll i = 1; i <= x; i++){
        ans = ans*i % mod;
    }
    return ans;
}

ll pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b % 2){
            ans  = ans*a % mod;
        }
        a = a*a % mod;
        b /= 2;
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;

    // C(n+m-1, m) = (n+m-1)! / (m! * (n-1)!)
    ll a = fact(n + m - 1);
    ll b = fact(m);
    ll c = fact(n-1);

    ll ans = a;
    ans = ans * pow(b, mod-2) % mod;
    ans = ans * pow(c, mod-2) % mod;
    cout << ans;
    return 0;
}

// Sample Input:
// 3 2
//
// Sample Output:
// 6