lucas 定理

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

$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$ 为质数

设 $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)\equiv 1+x^p \pmod p$ $p$ 为质数

这条结论的证明需要引入二项式定理。

$C^i_p=\dfrac{p!}{i!(p-i)!}$，因为 $p$ 是质数所以上下不能约分，而 $p!$ 一定能整除 $p$，所以对于中间的任意一项 $C^i_p (i\le p)$ 都整除 $p$

得到引理。

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

$\equiv (1+x^p)^s \times (1+x)^q\pmod p$ (由引理得)

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

$\therefore$ 指数为 $tp$ 的一项在前一个括号中，且其系数为 $C_s^t$

$\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 定理得证。