Định Lý Wilson & Định Lý Lucas¶

Tác giả: FPTOJ Team
Nội dung tham khảo từ: CP-Algorithms

Bản chất vấn đề¶

Định lý Wilson¶

Bài toán mở đầu: Tính $10! \mod 11$ mà không nhân tay 10 số? Vì $11$ nguyên tố, Wilson cho ngay đáp án $-1 \equiv 10 \pmod{11}$. Tổng quát: với $p$ nguyên tố, $(p-1)! \mod p$ luôn là $p-1$ — không cần tính giai thừa trực tiếp (bất khả khi $p$ lớn).

Wilson KHÔNG dùng để test nguyên tố trong thi đấu

Kiểm tra $(n-1)! \mod n$ tốn $O(n)$ phép nhân — với $n \approx 10^9$ sẽ TLE. Trong contest hãy dùng Miller-Rabin. Wilson chỉ hữu ích để biến đổi công thức giai thừa modulo, không phải để kiểm tra nguyên tố.

Định lý Lucas¶

Bài toán mở đầu: Tính $\binom{10^{18}}{10^9} \mod 5$? Không thể tính tử số trực tiếp (khổng lồ), và $5$ quá nhỏ để dùng nghịch đảo modulo thông thường qua giai thừa (vì $5 \mid$ mẫu số). Lucas tách $n, k$ thành các chữ số cơ số $5$ rồi nhân các tổ hợp nhỏ lại — mỗi tổ hợp nhỏ tính được bằng tay.

1. Định lý Wilson¶

Phát biểu¶

Với $p$ là số nguyên tố:

\[(p - 1)! \equiv -1 \pmod{p}\]

Hay tương đương: $(p-1)! + 1 \equiv 0 \pmod{p}$.

Ứng dụng¶

Kiểm tra số nguyên tố: $n$ là nguyên tố $\iff (n-1)! \equiv -1 \pmod{n}$. (Nhưng $O(N)$ — chậm.)
Tính $(p-1)! \mod p$ nhanh.

Ví dụ¶

$p$	$(p-1)!$	$(p-1)! \mod p$
2	$1! = 1$	$1 \equiv -1 \pmod{2}$ ✓
3	$2! = 2$	$2 \equiv -1 \pmod{3}$ ✓
5	$4! = 24$	$24 \mod 5 = 4 \equiv -1 \pmod{5}$ ✓
7	$6! = 720$	$720 \mod 7 = 6 \equiv -1 \pmod{7}$ ✓

Ý tưởng chứng minh¶

Với $p$ nguyên tố, mỗi $a \in \{1, 2, \ldots, p-1\}$ có nghịch đảo modulo $p$ duy nhất. Các phần tử khác 1 và $p-1$ ghép cặp với nghịch đảo của chúng. Do đó $(p-1)! = 1 \cdot (p-1) \cdot \prod (a \cdot a^{-1}) = p-1 \equiv -1$.

2. Định lý Lucas¶

Phát biểu¶

Cho $n, k$ và $p$ nguyên tố. Viết $n$ và $k$ trong cơ số $p$:

\[n = n_0 + n_1 p + n_2 p^2 + \ldots$$ $$k = k_0 + k_1 p + k_2 p^2 + \ldots\]

Thì:

\[\binom{n}{k} \equiv \prod_{i} \binom{n_i}{k_i} \pmod{p}\]

(với quy ước $\binom{n_i}{k_i} = 0$ nếu $k_i > n_i$).

Ứng dụng¶

Tính $\binom{n}{k} \mod p$ với $n, k$ rất lớn ($10^{18}$) và $p$ nhỏ (nguyên tố).

Trace chi tiết¶

Tính $\binom{22}{7} \mod 5$:

Bước 1: Viết 22 và 7 trong cơ số 5:

$22 = 4 \cdot 5 + 2 \Rightarrow (4, 2)_5$

$7 = 1 \cdot 5 + 2 \Rightarrow (1, 2)_5$

Bước 2: Áp dụng Lucas:

\[\binom{22}{7} \equiv \binom{4}{1} \cdot \binom{2}{2} \pmod{5}\]

\[= 4 \cdot 1 = 4\]

Kiểm tra: $\binom{22}{7} = 170544$, $170544 \mod 5 = 4$ ✓

3. Phân tích tính đúng đắn¶

Wilson¶

Với $p$ nguyên tố, mỗi $a \in \{2, 3, \ldots, p-2\}$ có nghịch đảo modulo $p$ duy nhất $a^{-1} \neq a$ (vì $a^2 \equiv 1 \pmod{p} \Rightarrow a = 1$ hoặc $a = p-1$). Do đó, các phần tử từ $2$ đến $p-2$ ghép cặp thành $(a, a^{-1})$ với $a \cdot a^{-1} \equiv 1$. Kết quả:

\[(p-1)! = 1 \cdot (p-1) \cdot \prod_{\text{cặp}} (a \cdot a^{-1}) = 1 \cdot (p-1) \cdot 1 = p-1 \equiv -1 \pmod{p}\]

Lucas¶

Viết $n$ và $k$ trong cơ số $p$: $n = (n_m \ldots n_1 n_0)_p$, $k = (k_m \ldots k_1 k_0)_p$.

Theo hệ thức Vandermonde modulo $p$:

\[\binom{n}{k} \equiv \prod_{i=0}^{m} \binom{n_i}{k_i} \pmod{p}\]

Đúng vì $(1+x)^n = \prod_{i} (1+x)^{n_i \cdot p^i} \equiv \prod_{i} (1+x^{p^i})^{n_i} \pmod{p}$ (theo Fermat nhỏ), và hệ số $x^k$ trong tích này chính là $\prod \binom{n_i}{k_i}$.

4. Đánh giá độ phức tạp¶

Thuật toán	Thời gian
Lucas với $p$ nguyên tố	$O(\log_p n \cdot p)$

Code minh họa¶