卢卡斯定理

在数论中，Lucas定理用于计算二项式系数 ${\tbinom {m}{n}}$ 被质数 p 除的所得的余数。

卢卡斯定理首次出现在1878年爱德华·卢卡斯[1]的论文中。

公式

对于非负整数m和n和素数p，同余式:

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

成立。其中：

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

并且

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

是m和n的p进制展开。当m < n时，二项式系数 ${\tbinom {m}{n}}=0$ 。

卢卡斯定理有多种证明方法。下面首先给出一种组合方法的证明，然后给出了一种基于母函数方法的证明。

本证明由Nathan Fine[2]给出。

对于素数p和n，满足1≤n≤p-1, 二项式系数

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

可被p整除。由此可得，在母函数中

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

应用数学归纳法可证，对于任意非负整数i，有

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

对于任意非负整数m和素数p，将m用p进制表示，即 $m=\sum _{i=0}^{k}m_{i}p^{i}$ ，其中k为非负整数、m_i 为整数且 0 ≤ m_i ≤ p-1。注意到

{\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}}

其中 n_i 是n的p进制表达的第i位。此即证明了本定理。

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

Edouard Lucas. . American Journal of Mathematics. 1878, 1 (2): 184–196. JSTOR 2369308. MR 1505161. doi:10.2307/2369308. (part 1);
Fine, Nathan. . American Mathematical Monthly. 1947, 54: 589–592. doi:10.2307/2304500.
Andrew Granville. (PDF). Canadian Mathematical Society Conference Proceedings. 1997, 20: 253–275 [2016-09-30]. MR 1483922. （原始内容 (PDF)存档于2017-02-02）.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.