# 卢卡斯定理

## 公式

${\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}$

${\displaystyle m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},}$

${\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}}$

## 结论

• 二项式系数 ${\displaystyle {\tbinom {m}{n}}}$  可被素数 p 整除当且仅当在p进制表达下n的某一位的数值大于m对应位的数值。

## 证明

### 基于母函数的证明

${\displaystyle {\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}}$

${\displaystyle (1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.}$

${\displaystyle (1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.}$

{\displaystyle {\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(1+X)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{m_{i}}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{p-1}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}},\end{aligned}}}

## 变型和推广

• 二项式系数 ${\displaystyle {\tbinom {m}{n}}}$  中含有质数p的幂次为算式n和m-n在p进制下进行相加计算的进位次数。(被称为Kummer's theorem.)
• Andrew Granville将卢卡斯定理由素数推广到了到素数的幂次[3]

## 参考资料

1. ^ Edouard Lucas. Théorie des Fonctions Numériques Simplement Périodiques. American Journal of Mathematics. 1878, 1 (2): 184–196. JSTOR 2369308. MR 1505161. doi:10.2307/2369308. (part 1);
2. ^ Fine, Nathan. Binomial coefficients modulo a prime. American Mathematical Monthly. 1947, 54: 589–592. doi:10.2307/2304500.
3. ^ Andrew Granville. Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers (PDF). Canadian Mathematical Society Conference Proceedings. 1997, 20: 253–275. MR 1483922. （原始内容 (PDF)存档于2017-02-02）.