Lucas定理证明
wangyanjing
·
·
算法·理论
感谢这篇文章的思路启发。
Lucas 定理：
C_n^m \bmod P = (C_{\lfloor\frac{n}{P}\rfloor} ^ {\lfloor \frac{m}{P} \rfloor} \cdot C_{n \bmod P} ^ {m \bmod P} )\bmod P
其中：n \ge m，P 为质数。
记：a = \lfloor\frac{n}{P}\rfloor,b = \lfloor\frac{m}{P}\rfloor,c = n \bmod P,d = m \bmod P。
那么：n = aP + c,m = bP+d。
当 n \bmod P < m \bmod P 时，有：C_n^m \bmod P = 0。
证：
易得此时 n\ge P,a>b, c<d。
记：f(n) 为最大正整数 i，使得 p^i | n。
易得：f(ab) = f(a) + f(b)。
注意到：
f(n!) = \sum_{i = 1}^{\lfloor\log_Pn\rfloor} \lfloor \frac{n}{P^i} \rfloor
由于：C_{n} ^m = \frac{n!}{m!(n-m)!}。
那么，只需证：f(n!) > f(m!) + f((n-m)!)。
注意到：(\sum_{i = 1}^{\lfloor\log_Pn\rfloor} \lfloor \frac{n}{P^i} \rfloor - \lfloor \frac{m}{P^i} \rfloor - \lfloor \frac{n-m}{P^i} \rfloor)>0。
证：
注意到： \lfloor \frac{n}{P^i} \rfloor \ge \lfloor \frac{m}{P^i} \rfloor + \lfloor \frac{n-m}{P^i} \rfloor。
当 i = 1 时：
\lfloor \frac{n}{P} \rfloor - \lfloor \frac{m}{P} \rfloor - \lfloor \frac{n-m}{P} \rfloor = a-b - \lfloor \frac{aP-bP+c-d}{P}\rfloor
\because c-d<0 \therefore \lfloor \frac{aP-bP+c-d}{P} \rfloor = a-b-1
\therefore \lfloor \frac{n}{P} \rfloor - \lfloor \frac{m}{P} \rfloor - \lfloor \frac{n-m}{P} \rfloor = 1
\therefore (\sum_{i = 1}^{\lfloor\log_Pn\rfloor} \lfloor \frac{n}{P^i} \rfloor - \lfloor \frac{m}{P^i} \rfloor - \lfloor \frac{n-m}{P^i} \rfloor)>0
证毕！
现在讨论 m \bmod P \le n \bmod P 的情况。
注意到对于 C_P^i，有：C_P^i = P \cdot \frac{C_{P-1}^{i-1}}{i} (i\in[1,P-1])。
证：
P \cdot \frac{C_{P-1}^{i-1}}{i} = \frac{(P-1)! P}{(i-1)! i (P-1-(i-1))!}= \frac{P!}{i!(P-i)!} = C_P^i
\therefore C_P^i \equiv P \cdot \frac{C_{P-1}^{i-1}}{i} \equiv P \cdot(C_{P-1}^{i-1} \cdot \text{inv}(i)) \equiv 0 (\bmod P)
\therefore (1+x) ^P \equiv \sum_{i = 0}^P C_P^ix^i \equiv 1 + x^P (\bmod P)
\begin{aligned} (1+x) ^ n \\& \equiv (1+x)^{Pa + c} \\& \equiv (1+x)^{Pa} \cdot (1+x) ^c \\& \equiv ((1+x)^P)^a \cdot (1+x)^c \\& \equiv (1+x^P)^a \cdot (1+x)^c \\ & \equiv (\sum_{i = 0}^a C_a^i x^{Pi})(\sum_{i = 0}^c C_c^i x^i) \\& \equiv \sum_{i = 0}^a \sum_{j = 0}^c C_a^i C_c^j x^{Pi+j} (\bmod P) \end{aligned}
\because (1+x) ^n = \sum_{i = 0}^n C_n^i x^i
\therefore \sum_{i = 0}^n C_n^i x^i \equiv\sum_{i = 0}^a \sum_{j = 0}^c C_a^i C_c^j x^{Pi+j} (\bmod P)
注意到：\forall i\in[0,a] \forall j\in [0,c] 有：Pi +j 不可重。
设存在 l,r，使得 Pl+r = Pi+j，且 [l \ne i] + [r \ne j] \ge 1。
\because Pl + r = Pi + j \therefore (Pl+r) \bmod P = (Pi+j) \bmod P \therefore r = j
\therefore Pl+r - r = Pi +j - j \therefore Pl = Pi
\because P \ne 0 \therefore l = i \therefore [l \ne i] + [r \ne j] = 0 < 1
故假设不成立。
那么：
C_n^m x^m \equiv C_a^b C_c^d x^{Pb+d} \equiv C_a^b C_c^d x^m (\bmod P)
\therefore C_n^m \equiv C_a^b C_c^d (\bmod P)
证毕！