【初等数论】卢卡斯定理的证明

Lucas定理

? 对于质数\(p\)，有

? \(\begin{equation} \binom{n}{m} \end{equation}\equiv\binom{n\bmod p}{m\bmod p}\cdot\binom{\lfloor \frac{n}{p}\rfloor}{\lfloor \frac{m}{p}\rfloor}\pmod{p}\)

该定理主要用于对大组合数取模。

引理：

1. 二项式定理

   \((a + b)^{n}= \sum_{i=0}^{n}C_n^ra^rb^{n-r}\)

2. 费马小定理

   对于质数\(p\)，\((1+x)^p \equiv (1+x^p)\pmod{p}\)

证明过程：

? 令\(n = sp+q,m=tp+r\)，其中\(s = \lfloor \frac{n}{p}\rfloor,t = \lfloor \frac{m}{p}\rfloor\)

? 考虑二项式\((1+x)^n\)的同余变换：

? \((1+x)^n = (1+x)^{sp} \cdot (1+x)^q\)

\(=\lbrack (1+x)^p\rbrack^s\cdot(1+x)^q\)

\(\equiv(1+x^p)^s\cdot (1+x)^q \pmod{p}\)（费马小定理）

\(\equiv\sum_{i=0}^{s}\binom{s}{i}x^{pi}\cdot\sum_{j=0}^q \binom{q}{j}x^j\)（二项式定理）

? （右边）

? 同时，\((1+x)^n=(1+x)^{sp+q}=\sum_{k=0}^{sp+q}\binom{sp+q}{k}x^k\)（左边）

? 此时对比两式中某一项\(x^{tp+r}\)的系数。

? 左边：\(\binom{sp + q}{tp+r}x^{tp+r}\)

? 右边：\(\binom{s}{t}x^{tp}\cdot\binom{q}{r}x^q\)

? 那么 \(\binom{n}{m} \equiv \binom{s}{t}\cdot\binom{q}{r}\pmod{p}\)

? 证毕。

【初等数论】卢卡斯定理的证明

原文：https://www.cnblogs.com/TY02/p/11813194.html