在数论中，盧卡斯定理（）用于计算二项式系数\tbinom{m}{n}被质数 p除的所得的余数。
卢卡斯定理首次出现在1878年法國數學家爱德华·卢卡斯的论文中。
公式
对于非负整数m和n和素数p， 同余式:
: \binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p,
成立。其中：
: m=m_kp^k+m_{k-1}p^{k-1}+\cdots +m_1p+m_0,
并且
: n=n_kp^k+n_{k-1}p^{k-1}+\cdots +n_1p+n_0
是m和n的p进制展开。当m时，二项式系数 \tbinom{m}{n} = 0。
推论
二项式系数 \tbinom{m}{n} 可被素数p整除当且仅当在p进制表达下n的某一位的数值大于m对应位的数值。
这是 庫默爾定理 的一个特殊情况。
证明
卢卡斯定理有多种证明方法。 下面首先给出一种组合方法的证明，然后给出了一种基于母函数方法的证明。
组合证明
设M为m元集，将其划分为m_i个长度为p^i的循环。然后这些循环中的每一个都可以单独轮换，因此作为循环群{C_p}^i的笛卡尔积的群G作用于M。因此，它也作用于大小为n的子集N。由于G中的元素数量是p的幂，因此它的任何轨道都是如此。因此，为了计算 \tbinom{m}{n} 模p，我们只需要考虑这个群作用的不动点。不动点是一些循环的并集。准确地说，可以通过对k-i的归纳来证明，N必须恰好有n_i个长度为p^i的循环。因此，N的个数正好是 \prod_{i=0}^k\binom{m_i}{n_i}\pmod{p}。
基于母函数的证明
本证明由Nathan Fine给出。
对于素数p和n，满足1\leq n\leq p-1, 二项式系数
: \binom p n = \frac{p \cdot (p-1) \cdots (p-n+1)}{n \cdot (n-1) \cdots 1}
可被p整除。由此可得，在母函数中
: (1+X)^p\equiv1+X^p\pmod{p}.
应用数学归纳法可证，对于任意非负整数i，有
: (1+X)^{p^i}\equiv1+X^{p^i}\pmod{p}.
对于任意非负整数m和素数p，将m用p进制表示，即m=\sum_{i=0}^{k}m_ip^i ，其中k为非负整数、m_i为整数且0\leq m_i\leq p-1。注意到
: \begin{align}
\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_ip^i}\right)\\
& =\prod_{i=0}^{k}\left(\sum_{n_i=0}^{p-1}\binom{m_i}{n_i}X^{n_ip^i}\right)=\sum_{n=0}^{m}\left(\prod_{i=0}^{k}\binom{m_i}{n_i}\right)X^n
\pmod{p},
\end{align}
其中n_i是n的p进制表达的第i位。此即证明了本定理。
变型和推广
- 二项式系数 \tbinom{m}{n} 中含有质数p的幂次为算式n和m-n在p进制下进行相加计算的进位次数。(被称为庫默爾定理.)
- Andrew Granville将卢卡斯定理由素数推广到了到素数的幂次。
参考资料
外部链接
*
- Alternate Proof of Lucas'Theorem
评论 (0)