Wiki › Thuật toán › Toán học › Lucas Theorem và Số học Modular Nâng cao

Lucas Theorem và Số học Modular Nâng cao

huunguyen Updated Tháng sáu 1, 2026

Khi cần tính $(\binom{n}{k}) mod p$ mà $n, k$ rất lớn (tới $10^{18}$ ) còn $p$ là số nguyên tố nhỏ, ta không thể tính trực tiếp giai thừa vì $n!$ vượt xa mọi kiểu số. Định lý Lucas đưa bài toán về việc nhân các tổ hợp nhỏ theo từng chữ số trong cơ số $p$ , đạt $O (\log_{p} n)$ thay vì $O (n)$ . Trang này còn bàn các công cụ số học modular nâng cao thường đi kèm: nghịch đảo modular, CRT (gộp kết quả khi $p$ không nguyên tố), Cipolla (căn bậc hai modulo $p$ ) và căn nguyên thủy.

Ý tưởng / Trực giác

Vì sao Lucas đúng

Mấu chốt nằm ở một đẳng thức đa thức trên trường $𝔽_{p}$ . Với $p$ nguyên tố, tam giác Pascal "sụp" theo modulo $p$ :

$(1 + x)^{p} \equiv 1 + x^{p} (\mod p) .$

Lý do: khai triển nhị thức cho $(\binom{p}{i})$ với $0 < i < p$ , mà $(\binom{p}{i}) = \frac{p!}{i! (p - i)!}$ chứa thừa số $p$ ở tử nhưng mẫu $i! (p - i)!$ không chia hết cho $p$ (vì mọi thừa số đều $< p$ ), nên $(\binom{p}{i}) \equiv 0 (\mod p)$ . Chỉ còn hai số hạng đầu và cuối.

Bây giờ viết $n$ trong cơ số $p$ : $n = n_{s} p^{s} + \dots + n_{1} p + n_{0}$ . Khi đó

$(1 + x)^{n} = \prod_{i = 0}^{s} (1 + x)^{n_{i} p^{i}} \equiv \prod_{i = 0}^{s} (1 + x^{p^{i}})^{n_{i}} (\mod p) .$

Hệ số của $x^{k}$ ở vế trái chính là $(\binom{n}{k})$ . Ở vế phải, vì mỗi nhân tử $(1 + x^{p^{i}})^{n_{i}}$ chỉ sinh ra các lũy thừa $x^{(số \leq n_{i}) \cdot p^{i}}$ , nên muốn ghép lại thành $x^{k}$ ta buộc phải lấy đúng chữ số $k_{i}$ (trong cơ số $p$ của $k$ ) từ nhân tử thứ $i$ . Mỗi cách góp cho hệ số $(\binom{n_{i}}{k_{i}})$ . Nhân lại:

$(\binom{n}{k}) \equiv \prod_{i = 0}^{s} (\binom{n_{i}}{k_{i}}) (\mod p)$

Hệ quả quan trọng: nếu bất kỳ chữ số nào thỏa $k_{i} > n_{i}$ thì $(\binom{n_{i}}{k_{i}}) = 0$ , kéo theo cả tích bằng $0$ . Đây cũng là định lý Kummer ở dạng gọn: $(\binom{n}{k})$ chia hết cho $p$ khi và chỉ khi có "nhớ" lúc cộng $k + (n - k)$ trong cơ số $p$ .

Vì sao cần nghịch đảo modular

Để tính $(\binom{a}{b}) = \frac{a!}{b! (a - b)!} mod p$ với $a, b < p$ , ta không chia được trực tiếp trong số học modular. Thay vào đó nhân với nghịch đảo $b!^{- 1}$ . Vì $p$ nguyên tố và $b! ≢ 0$ , định lý Fermat nhỏ cho $b!^{- 1} \equiv (b!)^{p - 2} (\mod p)$ . Đây là lý do mọi cài đặt đều có hàm power (lũy thừa nhanh).

Ví dụ chạy tay

Tính $(\binom{13}{4}) mod 3$ . Giá trị thật là $(\binom{13}{4}) = 715 = 3 \cdot 238 + 1$ , nên đáp án phải là $1$ . Xem Lucas tái tạo điều đó.

Đổi $13$ và $4$ sang cơ số $3$ :

 n = 13 = (1 1 1)_3      vì 13 = 1*9 + 1*3 + 1
 k =  4 = (0 1 1)_3      vì  4 = 0*9 + 1*3 + 1
          ^   ^   ^
        p^2  p^1 p^0

Ghép theo từng cột chữ số (mỗi cột một tổ hợp nhỏ $(\binom{n_{i}}{k_{i}})$ ):

 vị trí i :   2     1     0
 n_i      :   1     1     1
 k_i      :   0     1     1
 ------------------------------
 C(n_i,k_i):  C(1,0) C(1,1) C(1,1)
            =   1  *   1  *   1   = 1   (mod 3)

Vậy $(\binom{13}{4}) \equiv 1 (\mod 3)$ — khớp.

Một ví dụ cho thấy kết quả $0$ : $(\binom{6}{4}) mod 5$ . Ta có $6 = (1 1)_{5}$ , $4 = (0 4)_{5}$ :

 i        :   1     0
 n_i      :   1     0
 k_i      :   0     4
            C(1,0) C(0,4)
          =   1   *  0     = 0   (mod 5)

Tại cột $0$ , $k_{0} = 4 > n_{0} = 0$ nên $(\binom{0}{4}) = 0$ , kéo cả tích về $0$ . Thật vậy $(\binom{6}{4}) = 15 = 3 \cdot 5$ , chia hết cho $5$ .

Cài đặt

Lucas cơ bản (một vài truy vấn, $p$ nhỏ)

// Lũy thừa nhanh: a^e mod p  — O(log e)
long long power(long long a, long long e, long long p) {
    long long r = 1; a %= p;
    while (e > 0) {
        if (e & 1) r = r * a % p;
        a = a * a % p;
        e >>= 1;
    }
    return r;
}

// C(n,k) mod p với n,k < p, tính trực tiếp tử/mẫu rồi nhân nghịch đảo
long long C_small(long long n, long long k, long long p) {
    if (k > n) return 0;
    long long num = 1, den = 1;
    for (long long i = 0; i < k; i++) {
        num = num * ((n - i) % p) % p;   // tử: n*(n-1)*...*(n-k+1)
        den = den * ((i + 1) % p) % p;   // mẫu: k!
    }
    return num * power(den, p - 2, p) % p; // chia = nhân nghịch đảo (Fermat)
}

// Lucas: tách theo từng chữ số cơ số p, đệ quy
long long lucas(long long n, long long k, long long p) {
    if (k == 0) return 1;          // chặn đáy: C(n,0)=1
    if (k > n)  return 0;          // chữ số nào k_i>n_i -> kết quả 0
    // C(n,k) = C(n%p, k%p) * C(n/p, k/p)
    return C_small(n % p, k % p, p) * lucas(n / p, k / p, p) % p;
}

Lucas tối ưu cho nhiều truy vấn — precompute giai thừa mod $p$

Khi $p$ cố định và có nhiều truy vấn, tiền xử lý fact[] và inv_fact[] để mỗi $(\binom{n_{i}}{k_{i}})$ tính trong $O (1)$ :

const int MAXP = 1e6 + 5;
long long fact[MAXP], inv_fact[MAXP], P;

void precompute_lucas(long long p) {
    P = p;
    fact[0] = 1;
    for (int i = 1; i < p; i++) fact[i] = fact[i-1] * i % p;
    inv_fact[p-1] = power(fact[p-1], p-2, p);          // nghịch đảo của (p-1)!
    for (int i = p-2; i >= 0; i--)                      // truy hồi ngược: rẻ hơn
        inv_fact[i] = inv_fact[i+1] * (i+1) % p;
}

long long C_lucas(long long n, long long k) {
    if (k > n || k < 0) return 0;
    long long ans = 1;
    while (n > 0 || k > 0) {            // duyệt từng chữ số cơ số P
        long long ni = n % P, ki = k % P;
        if (ki > ni) return 0;
        ans = ans * fact[ni] % P * inv_fact[ki] % P * inv_fact[ni-ki] % P;
        n /= P; k /= P;
    }
    return ans;
}

Khi modulo KHÔNG nguyên tố: Lucas + CRT

Nếu $m = p_{1}^{a_{1}} \dots p_{t}^{a_{t}}$ không nguyên tố, ta tính $(\binom{n}{k}) mod p_{j}^{a_{j}}$ (bằng định lý Andrew Granville / Lucas mở rộng) rồi gộp bằng CRT. Phần lõi CRT:

// Nghịch đảo modular tổng quát qua Euclid mở rộng (mod bất kỳ, gcd phải = 1)
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1, g = ext_gcd(b, a % b, x1, y1);
    x = y1; y = x1 - (a / b) * y1;
    return g;
}
long long inv_mod(long long a, long long m) {
    long long x, y;
    if (ext_gcd((a % m + m) % m, m, x, y) != 1) return -1; // không tồn tại
    return (x % m + m) % m;
}

// Gộp hệ x ≡ r1 (mod m1), x ≡ r2 (mod m2) với gcd(m1,m2)=1
long long crt(long long r1, long long m1, long long r2, long long m2) {
    long long inv = inv_mod(m1 % m2, m2);
    long long t = ((r2 - r1) % m2 + m2) % m2 * inv % m2;
    return r1 + t * m1;   // nghiệm theo mod m1*m2
}

Cipolla — căn bậc hai modulo số nguyên tố lẻ

Tìm $x$ với $x^{2} \equiv n (\mod p)$ . Điều kiện tồn tại (ký hiệu Legendre $= 1$ ): $n^{(p - 1) / 2} \equiv 1$ .

// Trả về một nghiệm x của x^2 ≡ n (mod p), hoặc -1 nếu vô nghiệm
long long cipolla(long long n, long long p) {
    n %= p;
    if (n == 0) return 0;
    if (power(n, (p-1)/2, p) != 1) return -1;       // không phải thặng dư bậc 2
    if (p % 4 == 3) return power(n, (p+1)/4, p);     // công thức tắt

    long long a = 0;                                  // tìm a: a^2-n là phi-thặng-dư
    while (power(((a*a - n) % p + p) % p, (p-1)/2, p) != p - 1) a++;
    long long w2 = ((a*a - n) % p + p) % p;          // "i^2" trong GF(p^2)

    // số phức (a + sqrt(w2)); lũy thừa (p+1)/2 trong GF(p^2)
    using P2 = pair<long long,long long>;
    auto mul = [&](P2 X, P2 Y) -> P2 {
        return { (X.first*Y.first + X.second%p*Y.second%p*w2) % p,
                 (X.first*Y.second + X.second*Y.first) % p };
    };
    P2 res = {1, 0}, base = {a, 1};
    for (long long e = (p+1)/2; e > 0; e >>= 1) {
        if (e & 1) res = mul(res, base);
        base = mul(base, base);
    }
    return min(res.first, p - res.first);            // res.second luôn = 0
}

Căn nguyên thủy (primitive root)

$g$ là căn nguyên thủy mod $p$ nếu cấp của $g$ đúng bằng $p - 1$ (tức $g^{1}, \dots, g^{p - 1}$ là hoán vị của $1 . . p - 1$ ). Cần cho logarithm rời rạc, NTT...

bool is_primitive_root(long long g, long long p, vector<long long>& qs) {
    for (long long q : qs)                    // qs = các ước nguyên tố của p-1
        if (power(g, (p-1)/q, p) == 1) return false;
    return true;
}
long long find_primitive_root(long long p, vector<long long> qs) {
    for (long long g = 2; ; g++)
        if (is_primitive_root(g, p, qs)) return g;
}

Độ phức tạp

Thao tác	Thời gian	Bộ nhớ	Vì sao
Lucas cơ bản / truy vấn	$O (\log_{p} n \cdot p)$	$O (1)$	có $\log_{p} n$ chữ số, mỗi chữ số gọi `C_small` tốn $O (p)$ vòng lặp
Lucas precompute / truy vấn	$O (\log_{p} n)$	$O (p)$	tiền xử lý `fact/inv_fact` một lần $O (p)$ ; mỗi chữ số tra cứu $O (1)$
`power` (lũy thừa nhanh)	$O (\log e)$	$O (1)$	bình phương lặp, mỗi bước giảm nửa số mũ
Cipolla	$O (\log p)$ kỳ vọng	$O (1)$	dò $a$ trung bình $~$ vài bước (nửa số là phi-thặng-dư), rồi lũy thừa GF $(p^{2})$ tốn $O (\log p)$
CRT gộp 2 đồng dư	$O (\log m)$	$O (1)$	chi phí một nghịch đảo modular

Lý do cốt lõi Lucas nhanh: số chữ số của $n$ trong cơ số $p$ là $⌊ \log_{p} n ⌋ + 1$ . Với $n = 10^{18}$ và $p \approx 10^{6}$ thì chỉ khoảng $3$ chữ số — gần như tức thời.

⚠️ Lỗi thường gặp

Tràn số khi nhân. Tích fact[ni] * inv_fact[ki] * inv_fact[ni-ki] với $p$ cỡ $10^{6}$ vẫn an toàn trong long long nếu lấy % P sau mỗi phép nhân. Nếu gộp ba thừa số rồi mới mod, hoặc dùng int, sẽ tràn. Luôn a = a * b % p từng bước, và biến trung gian là long long.
Modulo âm. Trong Cipolla và CRT có hiệu a*a - n hay r2 - r1 có thể âm; phải chuẩn hóa ((x % p) + p) % p. Quên + p cho kết quả sai hoặc chỉ số mảng âm.
Dùng nghịch đảo Fermat khi $p$ không nguyên tố. $a^{p - 2}$ chỉ là nghịch đảo khi $p$ nguyên tố. Với modulo hợp số phải dùng inv_mod (Euclid mở rộng) và kiểm tra $gcd (a, m) = 1$ — nếu không nguyên tố cùng nhau thì nghịch đảo không tồn tại, không được trả bừa.
Áp Lucas khi $p$ KHÔNG nguyên tố. Lucas chỉ đúng cho $p$ nguyên tố. Với modulo như $m = 10^{9}$ (không nguyên tố) hay $m = 12$ phải tách thừa số nguyên tố + CRT, không được gọi lucas(n, k, m) thẳng.
Quên trường hợp $k > n$ ở từng chữ số. Nhiều người chỉ kiểm tra $k > n$ ở đầu mà quên rằng ngay cả khi $k \leq n$ tổng thể, vẫn có thể $k_{i} > n_{i}$ tại một cột — lúc đó kết quả phải là $0$ . Vòng lặp C_lucas phải return 0 ngay khi gặp ki > ni.
Precompute thiếu phần tử / sai biên. fact[] và inv_fact[] cần đủ chỉ số tới $p - 1$ (không phải tới $n$ ). Cấp phát mảng nhỏ hơn $p$ gây truy cập ngoài biên; ngược lại đừng cố tạo mảng tới $n = 10^{18}$ .
Cipolla với $n \equiv 0$ hoặc $p = 2$ . Phải xử lý riêng $n mod p = 0$ (nghiệm $0$ ) và tránh dùng công thức cho $p$ chẵn; thuật toán chỉ đúng cho $p$ nguyên tố lẻ.

Biến thể / Mở rộng

Định lý Kummer & lũy thừa của $p$ trong $(\binom{n}{k})$ : số mũ của $p$ trong $(\binom{n}{k})$ bằng số lần "nhớ" khi cộng $k + (n - k)$ trong cơ số $p$ . Hữu ích khi cần biết $(\binom{n}{k})$ có chia hết cho $p$ không.
Lucas mở rộng (Andrew Granville) cho $(\binom{n}{k}) mod p^{a}$ , kết hợp CRT để xử lý modulo hợp số bất kỳ.
Xem thêm các kỹ thuật nền tảng tại Toán học: số học modular, nghịch đảo, lũy thừa nhanh.

Bài tập luyện

Mã Số Bò (cowids) — (Intermediate) dùng $(\binom{m}{j})$ để đếm số nhị phân có đúng $K$ bit $1$ và "đi tới" số thứ $N$ ; luyện ý nghĩa tổ hợp của hệ số nhị thức.
Tự giúp mình (helpself) — (Advanced) tính tổng trên tất cả $2^{N}$ tập con modulo $10^{9} + 7$ ; luyện đếm tổ hợp và rút gọn lũy thừa $2^{k} mod p$ .
Số học mô-đun (modarith) — (Advanced) đếm hàm thỏa phương trình $k \cdot f (x) \equiv f (k x)$ với $p$ nguyên tố lẻ; luyện cấp nhân (multiplicative order), căn nguyên thủy và lũy thừa modular.
Năng Lực Bò Gold (cowmpetg) — (Veteran) đếm dãy hợp lệ với $N \leq 10^{9}$ modulo $10^{9} + 7$ ; cần hệ số nhị thức mod $p$ ở quy mô lớn — đúng đất diễn của Lucas/nghịch đảo modular.
HILO (hilo21) — (Master) tổng trên $N!$ hoán vị modulo $10^{9} + 7$ ; bài tổ hợp modular nặng, tổng hợp giai thừa, nghịch đảo và đếm có dấu.