Why this matters when you build with AI
The previous lesson builds a factorial table, and that table needs two things. The modulus must be prime, and the largest n must be below the modulus. Many problems break one of these. The modulus might be 6 or 1000000 (not prime), or n might be 10^18 (far too large for a table). An AI tool that has learned the factorial method often uses it anyway. The code compiles, the sample passes, and the answer is wrong on the real tests.
Here is what happens in practice, from our runs.
- Pascal's rule written with the loop going the wrong way prints a row that is not a binomial row. For row 5 it printed
1 5 14 28 42 42. The correct row is1 5 10 10 5 1. - Lucas' theorem with the composite modulus 6 printed 0 for C(7, 2). The true value is 21, and 21 leaves 3 modulo 6. Nothing was reported as an error.
- The factorial inverse for modulus 6 is not defined. Python's built-in
pow(2, -1, 6)raisesValueError: base is not invertible for the given modulus, but a C++ program using the power trick does not raise anything. It prints a wrong number.
This lesson covers two methods. Pascal's rule works for any modulus and any n that is small enough to build a table. Lucas' theorem works for a prime modulus and any n, as long as the modulus is small enough for a table of size p. The sample code is C++17, compiled with g++ -std=c++17 -O2 -Wall -Wextra using GCC 15.2. The output lines below are from our runs. Your output should match them exactly, because the arithmetic does not depend on the machine.
Pascal's rule
Pascal's rule says that C(n, k) = C(n - 1, k - 1) + C(n - 1, k). Read it as a choice. Take one fixed item from n items. Either the subset contains it, which leaves k - 1 items to pick from the other n - 1, or it does not, which leaves k items to pick from the other n - 1.
Build the triangle row by row. Row 0 is 1. Row 4 is 1 4 6 4 1, because 4 and 6 come from the row above: 1 + 3 = 4 and 3 + 3 = 6.
Pascal's rule has no division, so it works for every modulus. That is the reason to prefer it when the modulus is 6, 12, 100, or any number that is not prime. The cost is time and memory. Filling a table for every n up to N takes about N^2 / 2 additions. For N = 5000, a full table of 64-bit numbers is about 200 MB.
The row-by-row memory trick
We do not need the whole triangle at once. To get row i from row i - 1, each new entry uses two old entries. If we store only one row, the update must read the old values before they are overwritten. Going from k = i down to k = 1 does this. When we write row[k], the value row[k - 1] is still the old one, because we have not reached it yet.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Row n of Pascal's triangle modulo m. Works for any m >= 1, prime or not.
vector<ll> pascal_row(int n, ll m) {
vector<ll> row(n + 1, 0);
row[0] = 1 % m;
for (int i = 1; i <= n; i++)
for (int k = i; k >= 1; k--)
row[k] = (row[k] + row[k - 1]) % m;
return row;
}
int main() {
for (ll m : {6LL, 7LL}) {
cout << "row 6 mod " << m << ":";
for (ll v : pascal_row(6, m)) cout << ' ' << v;
cout << "\n";
}
cout << "row 5 mod 1000000007:";
for (ll v : pascal_row(5, 1000000007LL)) cout << ' ' << v;
cout << "\n";
return 0;
}Compiled and run, it printed:
row 6 mod 6: 1 0 3 2 3 0 1
row 6 mod 7: 1 6 1 6 1 6 1
row 5 mod 1000000007: 1 5 10 10 5 1Check row 6 by hand. C(6, 2) is 15, and 15 leaves 3 modulo 6. C(6, 3) is 20, and 20 leaves 2. Both match. Modulo 7, every entry of row 6 is 1 or 6, which matches 15 leaves 1 and 6 leaves 6.
The loop direction is the whole trick. Here is the same code with the inner loop going up.
// Wrong: k goes up, so row[k - 1] already holds the new value when row[k] reads it.
for (int i = 1; i <= n; i++)
for (int k = 1; k <= i; k++)
row[k] = row[k] + row[k - 1];With n = 5 and row starting as 1 0 0 0 0 0, this printed 1 5 14 28 42 42. The entries grow too fast, because each entry was added to a value that already contained the row above it. That run is the reason for the rule: update from high k to low k.
Checking Pascal against exact values
To make sure the rolling row is correct, we compared it with an exact table for n up to 60. The exact table fits in 64-bit integers, because C(60, 30) is about 1.18 times 10^17. The moduli were 1, 2, 6, 12, 100, 997 and 1000000007. The rolling row matched on all 13237 pairs.
Pascal's rule is the right tool when:
- the modulus is not prime, or
- n is small, up to a few thousand, and you need many rows or many values.
It is the wrong tool when n is 10^18. No table can hold that many rows.
Lucas' theorem
Lucas' theorem handles a prime modulus p and any n. The idea is to write n and k in base p, then multiply small binomials, one per digit.
Base p means each digit is between 0 and p - 1. The base-p digits of n are the numbers n_0, n_1, n_2, ..., where n = n_0 + n_1 times p + n_2 times p^2 + .... The digits of k are k_0, k_1, ... in the same way.
The theorem says that C(n, k) modulo p equals the product of C(n_i, k_i) modulo p over all digit positions i. If some k_i is larger than n_i, that factor is 0, so the whole product is 0.
Worked example with p = 5 and C(12, 3). Write 12 in base 5: 12 = 2 times 5 + 2, so its digits are (2, 2). Write 3 in base 5: 3 = 0 times 5 + 3, so its digits are (0, 3). The product is C(2, 0) times C(2, 3). Since 3 is larger than 2, C(2, 3) is 0. So C(12, 3) modulo 5 is 0.
Check it. C(12, 3) is 220, and 220 = 5 times 44, so the remainder is 0. The program below printed the same value.
A second example with p = 7 and C(50, 8). Write 50 in base 7: 50 = 1 times 49 + 0 times 7 + 1, so its digits are (1, 0, 1). Write 8 in base 7: 8 = 1 times 7 + 1, so its digits are (0, 1, 1). The product is C(1, 0) times C(0, 1) times C(1, 1). The middle factor is C(0, 1), which is 0. So the answer is 0. Python's exact value of C(50, 8) modulo 7 is also 0.
Why it works
For a prime p, the number (1 + x)^p equals 1 + x^p modulo p, because every middle binomial coefficient C(p, i) with 0 < i < p is divisible by p. Raising that identity to the power p again and again gives the digit rule. This is the standard proof idea. Lucas published the result in 1878, in "Sur les congruences des nombres euleriens et des coefficients differentiels des fonctions trigonometriques, suivant un module premier", Bulletin de la Société Mathématique de France 6, pages 49 to 54. A survey of its extensions by Romeo Meštrović (2014) is on arXiv as 1409.3820, titled "Lucas' theorem: its generalizations, extensions and applications (1878-2014)".
The code
The Lucas struct builds a table of factorials modulo p for 0 to p - 1, which is O(p) time and memory. Each query then splits n and k into digits and multiplies the small binomials. The main below checks the struct against an exact Pascal table mod p for every prime up to 13 and every n up to 120, and then prints the worked examples.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll pow_mod(ll a, ll e, ll m) {
ll r = 1 % m;
a %= m;
while (e > 0) {
if (e & 1) r = r * a % m;
a = a * a % m;
e >>= 1;
}
return r;
}
// Lucas' theorem: for a prime p and n = sum n_i p^i, k = sum k_i p^i,
// C(n, k) mod p = product of C(n_i, k_i) mod p over the base-p digits.
// Needs a prime p and a table of p factorials, so p should be at most about 1e6.
struct Lucas {
ll p;
vector<ll> fact, inv_fact;
explicit Lucas(ll p_) : p(p_), fact(p_), inv_fact(p_) {
fact[0] = 1;
for (ll i = 1; i < p; i++) fact[i] = fact[i - 1] * i % p;
inv_fact[p - 1] = pow_mod(fact[p - 1], p - 2, p);
for (ll i = p - 1; i >= 1; i--) inv_fact[i - 1] = inv_fact[i] * i % p;
}
// C(a, b) mod p for 0 <= a, b < p. Zero when b > a.
ll small(ll a, ll b) const {
if (b < 0 || b > a) return 0;
return fact[a] * inv_fact[b] % p * inv_fact[a - b] % p;
}
// C(n, k) mod p for any n, k >= 0. Zero when k > n.
ll C(ll n, ll k) const {
if (k < 0 || k > n) return 0;
ll res = 1;
while (n > 0 || k > 0) {
ll ni = n % p, ki = k % p;
if (ki > ni) return 0; // a digit of k is bigger than the digit of n
res = res * small(ni, ki) % p;
n /= p;
k /= p;
}
return res;
}
};
// Exact Pascal table mod p, used as the independent reference for small n.
vector<vector<ll>> pascal_mod(int N, ll p) {
vector<vector<ll>> P(N + 1, vector<ll>(N + 1, 0));
for (int n = 0; n <= N; n++) {
P[n][0] = 1 % p;
for (int k = 1; k <= n; k++) P[n][k] = (P[n - 1][k - 1] + P[n - 1][k]) % p;
}
return P;
}
int main() {
long long checked = 0;
for (ll p : {2LL, 3LL, 5LL, 7LL, 11LL, 13LL}) {
const int N = 120;
auto P = pascal_mod(N, p);
Lucas L(p);
for (int n = 0; n <= N; n++)
for (int k = -1; k <= n + 1; k++) {
ll want = (k < 0 || k > n) ? 0 : P[n][k];
if (L.C(n, k) != want) {
cout << "MISMATCH p=" << p << " n=" << n << " k=" << k << "\n";
return 1;
}
checked++;
}
}
cout << "Lucas agrees with Pascal on " << checked << " cases\n";
Lucas L5(5), L7(7);
cout << "C(12, 3) mod 5 = " << L5.C(12, 3) << "\n";
cout << "C(50, 8) mod 7 = " << L7.C(50, 8) << "\n";
cout << "C(1000000000000000000, 1) mod 1000003 = " << Lucas(1000003).C(1000000000000000000LL, 1) << "\n";
return 0;
}Compiled and run, it printed:
Lucas agrees with Pascal on 45738 cases
C(12, 3) mod 5 = 0
C(50, 8) mod 7 = 0
C(1000000000000000000, 1) mod 1000003 = 999976The check covers every n from 0 to 120 and every k from -1 to n + 1, for each of six primes. Python's exact math.comb checked 300 more random cases with n up to 10^18 and modulus up to 1000003. All 300 agreed.
Python version
Lucas' theorem is short in Python too. The digit loop is fast enough for every query in a contest, because it takes at most about 60 steps for n up to 10^18 when p = 2. This version uses comb on the small digits. The table is not needed, because the digits are small.
Its output is:
0 0 1 1
999976 999976The second line checks the answer against the exact value of comb(10**18, 1). The two numbers agree.
Worked problem: many queries with huge n
Statement. The first line gives a prime p with p at most 1000000. The second line gives Q, the number of queries. Each query line gives two integers n and k, with 0 <= n and 0 <= k, and both at most 10^18. For each query, print C(n, k) modulo p. Print 0 when k > n.
Limits: 1 to 100000 queries.
Sample input:
5 4
12 3
24 6
100 50
1000000000000000000 1Sample output:
0
1
1
0Solution. Build the Lucas table once for the given p. That costs O(p) time, which is at most 10^6 steps. Each query takes O(log_p n) multiplications, which is at most 60 for p = 2. The total time is O(p + Q log_p n).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll pow_mod(ll a, ll e, ll m) {
ll r = 1 % m;
a %= m;
while (e > 0) {
if (e & 1) r = r * a % m;
a = a * a % m;
e >>= 1;
}
return r;
}
struct Lucas {
ll p;
vector<ll> fact, inv_fact;
explicit Lucas(ll p_) : p(p_), fact(p_), inv_fact(p_) {
fact[0] = 1;
for (ll i = 1; i < p; i++) fact[i] = fact[i - 1] * i % p;
inv_fact[p - 1] = pow_mod(fact[p - 1], p - 2, p);
for (ll i = p - 1; i >= 1; i--) inv_fact[i - 1] = inv_fact[i] * i % p;
}
ll small(ll a, ll b) const {
if (b < 0 || b > a) return 0;
return fact[a] * inv_fact[b] % p * inv_fact[a - b] % p;
}
ll C(ll n, ll k) const {
if (k < 0 || k > n) return 0;
ll res = 1;
while (n > 0 || k > 0) {
ll ni = n % p, ki = k % p;
if (ki > ni) return 0;
res = res * small(ni, ki) % p;
n /= p;
k /= p;
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Input: a prime p (p <= 1000000), then Q, then Q lines "n k" with 0 <= n, k <= 1e18.
ll p;
int q;
cin >> p >> q;
Lucas L(p);
while (q--) {
ll n, k;
cin >> n >> k;
cout << L.C(n, k) << "\n";
}
return 0;
}Compiled and run on the sample input, it printed:
0
1
1
0Each answer matches the sample. For example, C(24, 6) is 134596, and 134596 leaves 1 modulo 5.
To test it, we wrote 40 random batches of 2000 queries each, for 80000 queries in total. Half the queries had n up to 400 and k from 0 to n + 3. The other half had n up to 10^18 and k up to 50, because Python's exact comb is slow for big k. The modulus was chosen from 2, 3, 5, 7, 11, 13, 101, 997 and 1000003. All 80000 answers matched Python's exact value taken modulo p.
Complexity
Pascal's rule takes O(n^2) time and O(n) memory with the row trick. It works for any modulus.
Lucas' theorem takes O(p) time and memory to build the factorial table, and O(log_p n) time per query. The table is only useful when p is small enough to store. For p = 10^9 + 7, the two tables would hold about 10^9 values each, which is about 16 GB of 64-bit numbers. Lucas' theorem is for small primes and huge n. The factorial method from the previous lesson is for large primes and small n.
Common mistakes
-
Using Lucas' theorem with a composite modulus. For p = 6 and C(7, 2), our program printed 0. The true value is 21, which leaves 3 modulo 6. The fix is Pascal's rule for small n, or the Chinese remainder theorem on the prime factors of the modulus. The cp-algorithms article "Binomial Coefficients" describes that approach for a square-free composite modulus.
-
Filling Pascal's row in the wrong direction. The symptom is a row that grows too fast, such as
1 5 14 28 42 42for row 5. The fix is to loop k from high to low. -
Forgetting that the table must be of size p, not n. For Lucas, the tables have p entries. A table of size n = 10^18 would never fit, and two tables of size p = 10^9 + 7 would need about 16 GB.
-
Using Pascal's rule for n near 10^18. The table has n^2 entries, so the program runs out of memory or time long before the answer is found.
A prompt to check AI output
Paste this into a new chat with your code and the answer it gave you.
Here is my C++ code for C(n, k) modulo m. Check it for these points and mark each one pass or fail:
1. If m is not prime, the code does not use factorial inverses.
2. If m is prime, the code uses Lucas' theorem only when n is large, and each base-p digit comparison returns 0 when the digit of k is bigger than the digit of n.
3. Pascal's rule, when used, updates the row from high k to low k.
4. The code handles k < 0 and k > n before any array index.
For each fail, give the smallest input that shows the error and the value an exact count gives for that input. Do not change the code yet.A good answer marks each point and gives a counterexample for each fail. For a composite modulus, the counterexample is C(7, 2) with m = 6, which has true value 3. Check the counterexample yourself with an exact count, because a model can state a wrong value with confidence.
Checklist
- Is the modulus prime? If not, use Pascal's rule for small n.
- Is n small enough for a table of n^2 entries? If not, you need Lucas, and the modulus must be prime.
- Is the modulus small enough for a factorial table of size p? If not, Lucas does not apply directly.
- In Pascal's row update, does the inner loop go from high k to low k?
- In Lucas, does every base-p digit comparison return 0 when the digit of k is bigger?
- Did you compare small cases against an exact count or an exact Pascal table?
Practice
Each practice problem has a hint. Try it before you read the answer under the line "Show the answer".
- Compute C(20, 6) modulo 3 by Lucas' theorem, by hand. Hint: write 20 and 6 in base 3. Then multiply the small binomials.
Show the answer In base 3, 20 is 2 times 9 + 0 times 3 + 2, so its digits are (2, 0, 2). And 6 is 0 times 9 + 2 times 3 + 0, so its digits are (0, 2, 0). The digit pairs are (2, 0), (0, 2) and (2, 0). The middle factor is C(0, 2), which is 0. So the answer is 0. Check: C(20, 6) is 38760, and 38760 leaves 0 modulo 3.
- Count the odd entries in rows 0 to 15 of Pascal's triangle. Hint: with p = 2, each base-2 digit of k must be at most the digit of n in the same place. Count the rows, then count the entries in each row that pass the test.
Show the answer
The answer is 81. An entry C(n, k) is odd exactly when every 1-bit of k is also a 1-bit of n. A row n with b one-bits has 2^b odd entries. Summed over rows 0 to 15, that gives 3^4 = 81. Python's exact comb gives 81 when it checks all 136 entries of those 16 rows.
- Compute C(10, 4) modulo 6 with Pascal's rule, not with factorials. Hint: the modulus 6 is not prime, so the factorial method does not apply. Build row 10 with the rolling row.
Show the answer The answer is 0. The exact value is 210, and 6 times 35 is 210. Pascal's rule on row 10 with modulus 6 also gives 0 at position 4, because every step is an exact sum modulo 6.
- You need C(n, k) modulo p = 1000003 for n = 10^6 and many values of k. Which method do you use, and why? Hint: compare n with p.
Show the answer Use the factorial method from the previous lesson. The modulus 1000003 is prime, and n = 10^6 is below it, so the table of factorials has size 10^6 and is valid. Lucas' theorem also gives the answer, but it is slower per query, because each query splits n into digits.
Exercise: implement Lucas and check it against Pascal
Write a Lucas function for a prime p. Check it against Pascal's rule on every n up to 300, every k from -1 to n + 1, and every prime from 2 to 13. Count the cases that agree. Then check it on 300 random pairs with n up to 10^18 against Python's exact comb.
Show the answer
The program in the solution section of this lesson does the first check. Its main runs with N = 120, and it printed 45738 agreeing cases. Change N to 300 to cover the exercise range, and the count becomes 276318.
For the second check, we used a copy of the same Lucas struct with a small dump mode. It printed 300 random triples (p, n, k), with n up to 10^18 and k up to 40. A short Python script read those lines and compared each value with math.comb(n, k) % p. The result was 300 cases and 0 mismatches. Your numbers should match ours if you use the same struct, but the random triples depend on the generator, so the exact cases may differ.
Summary
Use Pascal's rule with a rolling row for any modulus when n is small. Use Lucas' theorem for a prime modulus when n is huge and the modulus is small enough for a table of size p. The two methods do not replace each other, and each one has a range where it is wrong.