GCD/LCM, Euler's totient, nCr mod p
Scenario
You need to calculate 'N choose K' (Combinations) where N = 100,000. The factorial of 100,000 has over 400,000 digits. Standard math libraries will instantly overflow, even with 64-bit integers.
How do you calculate combinations of massive numbers modulo a prime without overflowing?
Why it exists
Competitive programming frequently tests combinatorial mathematics (e.g., 'How many valid permutations exist?'). Because factorials grow astronomically fast, these answers are always required modulo a prime. Fermat's Little Theorem and Modular Inverses provide the mathematical bridge to compute exact division under a modulo, making massive statistical algorithms programmable in standard memory.
Mental model
Normally, computing combinations involves division (N! / (K! * (N-K)!)). But in modular arithmetic, division doesn't exist. Instead, you multiply by a 'reciprocal' (the modular inverse), calculated using Fermat's Little Theorem.
Advanced CP Number Theory relies on a conceptual chain: GCD and LCM form the basics of divisibility. Euler's Totient describes prime properties, which yields Fermat's Little Theorem. This theorem finally gives us the ability to perform modular division, allowing us to compute massive Combinations (nCr) within standard memory limits.
Explanation
**1. GCD and LCM:**
The Greatest Common Divisor is found using the Euclidean Algorithm: `gcd(a, b) = gcd(b, a % b)` (with base case `gcd(a, 0) = a`). Every two steps, the modulo operation guarantees the numbers decrease by at least half, leading to its blazing-fast `O(log(min(a,b)))` complexity. The Least Common Multiple is mathematically tied to it: `lcm(a, b) = (a * b) / gcd(a, b)`. (Always divide first to prevent overflow: `a / gcd(a,b) * b`). Modern C++ provides `std::gcd` and `std::lcm` in `<numeric>`.
**2. Euler's Totient Function ($\\phi(n)$):**
This function counts how many integers from 1 to `n` are coprime to `n` (meaning `gcd(x, n) == 1`). If `n` is prime, $\\phi(n) = n - 1$. Euler's Theorem states that $B^{\\phi(M)} \\equiv 1 \\pmod M$. For a prime $M$, this directly becomes Fermat's Little Theorem!
**3. Modular Inverse & Fermat's Little Theorem:**
You cannot divide in modular arithmetic. To calculate `(A / B) % M`, you must compute `A * B^{-1} % M`.
If `M` is prime, Fermat's Little Theorem states that `B^{M-1} \\equiv 1 \\pmod M`. By splitting this, we get `B * B^{M-2} \\equiv 1 \\pmod M`. This proves that `B^{M-2}` acts as the exact multiplicative inverse (`B^{-1}`)! Therefore, to divide by `B`, you multiply by `B^{M-2} \\pmod M`. You can compute this instantly using Fast Power!
**4. Combinations (nCr mod P):**
Combinations are calculated as `N! / (K! * (N-K)!)`.
To do this modulo a prime `P`:
1. Precompute factorials up to N using an array: `fact[i] = (fact[i-1] * i) % P`, with the base case `fact[0] = 1`.
2. To divide by `K!`, multiply by its modular inverse: `fast_power(fact[K], P-2, P)`.
3. Complete the formula: `nCr = (fact[N] * inverse(fact[K]) % P * inverse(fact[N-K]) % P) % P`.
Code examples
nCr modulo P (using Fermat's Little Theorem)
long long fast_power(long long base, long long exp, long long mod) {
long long res = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return res;
}
// Modular Inverse using Fermat's Little Theorem (only if mod is Prime)
long long mod_inverse(long long n, long long p) {
return fast_power(n, p - 2, p);
}
long long nCr_mod_p(long long n, long long r, long long p, const vector<long long>& fact) {
if (r < 0 || r > n) return 0;
// N! * (R!)^-1 * ((N-R)!)^-1 (all modulo P)
long long num = fact[n];
long long den = (fact[r] * fact[n - r]) % p;
return (num * mod_inverse(den, p)) % p;
}Assuming the `fact` array is precomputed, this calculates exact combinations of massive sets modulo P in O(log P) time.
Key points
- Division is Inverse Multiplication: In modular arithmetic, you never divide. You multiply by the modular inverse.
- Precompute factorials: For nCr queries, precompute an array of factorials `O(N)` to answer queries in `O(log P)`.
Common mistakes
- Using Fermat's Little Theorem with non-primes: The trick `B^{M-2} % M` only works if `M` is a prime number (like 10^9+7). If `M` is composite, you cannot use Fermat's Little Theorem. You must use the Extended Euclidean Algorithm to find the modular inverse, which is much more complex.
Recall questions
- What is the formula to calculate the Least Common Multiple (LCM) of two numbers using their Greatest Common Divisor (GCD)?
- How does Fermat's Little Theorem allow us to perform division in modular arithmetic when the modulo `M` is prime?
- What does Euler's Totient function count?
Questions & answers
A developer writes a custom `gcd(a, b)` function. They call it on two massive Fibonacci numbers. The function finishes in less than a millisecond. How is the Euclidean algorithm able to be so fast on massive inputs?
The Euclidean algorithm uses the modulo operator iteratively `gcd(b, a % b)`. Every two steps, the numbers are guaranteed to decrease by at least half. Thus, its time complexity is O(log(min(a,b))), which takes fewer than 100 steps even for numbers up to 10^18.
Approach: Understand the logarithmic decay of the modulo operator in the Euclidean algorithm.
A junior developer needs to find the GCD of two numbers and writes a loop that tests every integer down from `min(a, b)`. It causes a TLE. What should they use instead?
They should use the Euclidean algorithm `gcd(b, a % b)`, which computes the GCD in O(log(min(a, b))) time, or simply use C++'s built-in `std::gcd`.
Approach: Know standard library built-ins for foundational math operations.
Continue learning
Previous: Sieve of Eratosthenes & prime factorization
Previous: Modular arithmetic & fast power