专栏文章

Lucas定理证明

wwangyanjing
算法·理论参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mjreoo17
此快照首次捕获于
2025/12/30 01:02
2 个月前
此快照最后确认于
2026/02/19 01:25
14 小时前
查看原文
感谢这篇文章的思路启发。
Lucas 定理：
Cnm mod P=(C⌊nP⌋⌊mP⌋⋅Cn mod Pm mod P) mod PC_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≥mn \ge m，PP 为质数。
记：a=⌊nP⌋,b=⌊mP⌋,c=n mod P,d=m mod Pa = \lfloor\frac{n}{P}\rfloor,b = \lfloor\frac{m}{P}\rfloor,c = n \bmod P,d = m \bmod P。
那么：n=aP+c,m=bP+dn = aP + c,m = bP+d。
当 n mod P<m mod Pn \bmod P < m \bmod P 时，有：Cnm mod P=0C_n^m \bmod P = 0。
证：
易得此时 n≥P,a>b,c<dn\ge P,a>b, c<d。
记：f(n)f(n) 为最大正整数 ii，使得 pi∣np^i | n。
易得：f(ab)=f(a)+f(b)f(ab) = f(a) + f(b)。
注意到：
f(n!)=∑i=1⌊log⁡Pn⌋⌊nPi⌋f(n!) = \sum_{i = 1}^{\lfloor\log_Pn\rfloor} \lfloor \frac{n}{P^i} \rfloor
由于：Cnm=n!m!(n−m)!C_{n} ^m = \frac{n!}{m!(n-m)!}。
那么，只需证：f(n!)>f(m!)+f((n−m)!)f(n!) > f(m!) + f((n-m)!)。
注意到：(∑i=1⌊log⁡Pn⌋⌊nPi⌋−⌊mPi⌋−⌊n−mPi⌋)>0(\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。
证：
注意到：⌊nPi⌋≥⌊mPi⌋+⌊n−mPi⌋ \lfloor \frac{n}{P^i} \rfloor \ge \lfloor \frac{m}{P^i} \rfloor + \lfloor \frac{n-m}{P^i} \rfloor。
当 i=1i = 1 时：
⌊nP⌋−⌊mP⌋−⌊n−mP⌋=a−b−⌊aP−bP+c−dP⌋ \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
∵c−d<0∴⌊aP−bP+c−dP⌋=a−b−1\because c-d<0 \therefore \lfloor \frac{aP-bP+c-d}{P} \rfloor = a-b-1
∴⌊nP⌋−⌊mP⌋−⌊n−mP⌋=1\therefore \lfloor \frac{n}{P} \rfloor - \lfloor \frac{m}{P} \rfloor - \lfloor \frac{n-m}{P} \rfloor = 1
∴(∑i=1⌊log⁡Pn⌋⌊nPi⌋−⌊mPi⌋−⌊n−mPi⌋)>0\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 mod P≤n mod Pm \bmod P \le n \bmod P 的情况。
注意到对于 CPiC_P^i，有：CPi=P⋅CP−1i−1i(i∈[1,P−1])C_P^i = P \cdot \frac{C_{P-1}^{i-1}}{i} (i\in[1,P-1])。
证：
P⋅CP−1i−1i=(P−1)!P(i−1)!i(P−1−(i−1))!=P!i!(P−i)!=CPiP \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
∴CPi≡P⋅CP−1i−1i≡P⋅(CP−1i−1⋅inv(i))≡0( mod P)\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)
∴(1+x)P≡∑i=0PCPixi≡1+xP( mod P)\therefore (1+x) ^P \equiv \sum_{i = 0}^P C_P^ix^i \equiv 1 + x^P (\bmod P)
(1+x)n≡(1+x)Pa+c≡(1+x)Pa⋅(1+x)c≡((1+x)P)a⋅(1+x)c≡(1+xP)a⋅(1+x)c≡(∑i=0aCaixPi)(∑i=0cCcixi)≡∑i=0a∑j=0cCaiCcjxPi+j( mod 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}
∵(1+x)n=∑i=0nCnixi\because (1+x) ^n = \sum_{i = 0}^n C_n^i x^i
∴∑i=0nCnixi≡∑i=0a∑j=0cCaiCcjxPi+j( mod P)\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)
注意到：∀i∈[0,a]∀j∈[0,c]\forall i\in[0,a] \forall j\in [0,c] 有：Pi+jPi +j 不可重。
设存在 l,rl,r，使得 Pl+r=Pi+jPl+r = Pi+j，且 [l≠i]+[r≠j]≥1[l \ne i] + [r \ne j] \ge 1。
∵Pl+r=Pi+j∴(Pl+r) mod P=(Pi+j) mod P∴r=j\because Pl + r = Pi + j \therefore (Pl+r) \bmod P = (Pi+j) \bmod P \therefore r = j
∴Pl+r−r=Pi+j−j∴Pl=Pi\therefore Pl+r - r = Pi +j - j \therefore Pl = Pi
∵P≠0∴l=i∴[l≠i]+[r≠j]=0<1\because P \ne 0 \therefore l = i \therefore [l \ne i] + [r \ne j] = 0 < 1
故假设不成立。
那么：
Cnmxm≡CabCcdxPb+d≡CabCcdxm( mod P)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)
∴Cnm≡CabCcd( mod P)\therefore C_n^m \equiv C_a^b C_c^d (\bmod P)
证毕！

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...