lucas 定理

· · 个人记录

2025.3.22 总结lucas 定理，其证明过程，以及exlucas。

Lucas 定理

### 证明1（类生成函数） 设 $n=sp+q,m=tp+r (q,r \le p)

我们要证的就转变为 C_n^m\equiv C_s^tC_q^r\pmod p p 为质数

我们引入一条结论

这条结论的证明需要引入二项式定理。 $(1+x)^p = C_p^0 x^0 + C_p^1x^1+ C_p^2x^2\cdots +C_p^{p-1}x^{p-1}+C_p^p x^p =1+C_p^1x^1+ C_p^2x^2\cdots +C_p^{p-1}x^{p-1}+x^p C^i_p=\dfrac{p!}{i!(p-i)!}$，因为 $p$ 是质数所以上下不能约分，而 $p!$ 一定能整除 $p$，所以对于中间的任意一项 $C^i_p (i\le p)$ 都整除 $p (1+x)^p =1+C_p^1x^1+ C_p^2x^2\cdots +C_p^{p-1}x^{p-1}+x^p \equiv 1+x^p\pmod p

得到引理。

根据二项式定理，我们可以把 C_n^m 看作 (1+x)^n 中 x^m 这一项的系数，于是我们尝试在 (1+x)^n 拼出系数 C_s^tC_q^r

(1+x)^n =(1+x)^{sp+q} =[(1+x)^p]^s\times (1+x)^q $\equiv (C_s^0x^{0}+C_s^1x^{p}+C_s^2x^{2p}\cdots C_s^{s-1}x^{(s-1)p}+C_s^sx^{sp})\times(C_q^0x^{0}+C_q^1x^{1}+C_q^2x^{2}\cdots C_q^{q-1}x^{(q-1)}+C_q^qx^{q}) \because n=sp+q,m=tp+r,m<n \therefore t<s,r<q

想找到 x^m=x^{tp+r}=x^{tp}x^r。

\because tp>q \therefore$ 指数为 $tp$ 的一项在前一个括号中，且其系数为 $C_s^t \because r<p \therefore$ 指数为 $r$ 的一项在后一个括号中，且其系数为 $C_q^r

我们便得到原来 (1+x)^n 中为 x^m 这一项为 C_s^t x^{tp} \times C_q^rx^r=C_s^tC_q^rx^{tp+r}=C_s^tC_q^rx^m

又有C_n^m 为 (1+x)^n 中 x^m 这一项的系数

所以 C_n^m\equiv C_s^tC_q^r\pmod p

即 C_n^m \equiv C_{\left\lfloor\ n /p\right\rfloor}^{\left\lfloor\ m/p\right\rfloor} C_{n\bmod p} ^ {m\bmod p} \pmod p p 为质数

lucas 定理得证。

证明2（）