[瞎搞]Lucas定理证明

求证

Cnm≡∏i=0kCnimimodp

其中 m=∑ki=0mipi ， n=∑ki=0nipi
p是质数。

首先，我们知道， n0=nmodp，m0=mmodp
那么原式相当于求证

Cnm≡C⌊np⌋⌊mp⌋∗Cnmodpmmodpmodp

这样就可以归纳一发证明整个定理了。

首先我们知道，对于任意的质数p

Cnp≡0modp，(n≠0或p)

这个式子是恒成立的。
那么我们对于任意的一个实数x有

(x+1)p=∑i=0pCipxi

在模p意义下有

(x+1)p≡(xp+1)modp

Ps:为了方便接下来的所有计算均在模p意义下进行。

我们对于任意一个整数m有

(x+1)m=(x+1)⌊mp⌋p∗(x+1)mmodp

(x+1)m=(xp+1)⌊mp⌋∗(x+1)mmodp

二项式定理展开

∑i=0mCimxi=(∑i=0⌊mp⌋Ci⌊mp⌋xpi)(∑i=0mmodpCimmodpxi)

那么等号左边当i=n时，等号右边唯一能组合出来x^n的就是x^(n\p*p)和x^(n mod p)
那么系数乘积也就相等。
证毕。