查看“︁卢卡斯定理”︁的源代码

在[[数论]]中，'''盧卡斯定理'''（{{lang-en|Lucas's theorem}}）用于计算二项式系数<math>\tbinom{m}{n}</math>被[[素数|质数]] <math>p</math>除的所得的余数。

卢卡斯定理首次出现在1878年[[法國]]數學家[[爱德华·卢卡斯]]<ref>{{Cite journal|title=Théorie des Fonctions Numériques Simplement Périodiques|author=Edouard Lucas|journal=[[American Journal of Mathematics]]|issue=2|doi=10.2307/2369308|year=1878|volume=1|pages=184–196|jstor=2369308|mr=1505161}} (part 1);</ref>的论文中。

== 公式 ==
对于非负整数<math>m</math>和<math>n</math>和素数<math>p</math>， 同余式:
: <math>\binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p,</math>
成立。其中：
: <math>m=m_kp^k+m_{k-1}p^{k-1}+\cdots +m_1p+m_0,</math>
并且
: <math>n=n_kp^k+n_{k-1}p^{k-1}+\cdots +n_1p+n_0</math>
是<math>m</math>和<math>n</math>的<math>p</math>进制展开。当<math>m<n</math>时，二项式系数 <math>\tbinom{m}{n} = 0</math>。

== 推论 ==
二项式系数 <math>\tbinom{m}{n}</math> 可被素数<math>p</math>整除当且仅当在<math>p</math>进制表达下<math>n</math>的某一位的数值大于<math>m</math>对应位的数值。
这是 [[庫默爾定理]] 的一个特殊情况。

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

=== 组合证明 ===
设<math>M</math>为<math>m</math>元集，将其划分为<math>m_i</math>个长度为<math>p^i</math>的循环。然后这些循环中的每一个都可以单独轮换，因此作为循环群<math>{C_p}^i</math>的笛卡尔积的群<math>G</math>作用于<math>M</math>。因此，它也作用于大小为''<math>n</math>''的子集<math>N</math>。由于<math>G</math>中的元素数量是<math>p</math>的幂，因此它的任何轨道都是如此。因此，为了计算 <math>\tbinom{m}{n}</math> 模<math>p</math>，我们只需要考虑这个群作用的不动点。不动点是一些循环的并集。准确地说，可以通过对<math>k-i</math>的归纳来证明，<math>N</math>必须恰好有<math>n_i</math>个长度为<math>p^i</math>的循环。因此，<math>N</math>的个数正好是 <math>\prod_{i=0}^k\binom{m_i}{n_i}\pmod{p}</math>。

=== 基于母函数的证明 ===
本证明由Nathan Fine<ref>{{Cite journal|title=Binomial coefficients modulo a prime|url=https://archive.org/details/sim_american-mathematical-monthly_1947-12_54_10/page/589|last=Fine|first=Nathan|journal=American Mathematical Monthly|doi=10.2307/2304500|year=1947|volume=54|pages=589–592}}</ref>给出。

对于素数<math>p</math>和''<math>n</math>''，满足<math>1\leq n\leq p-1</math>, 二项式系数
: <math> \binom p n = \frac{p \cdot (p-1) \cdots (p-n+1)}{n \cdot (n-1) \cdots 1} </math>
可被<math>p</math>整除。由此可得，在母函数中
: <math>(1+X)^p\equiv1+X^p\pmod{p}.</math>
应用数学归纳法可证，对于任意非负整数<math>i</math>，有
: <math>(1+X)^{p^i}\equiv1+X^{p^i}\pmod{p}.</math>
对于任意非负整数<math>m</math>和素数<math>p</math>，将<math>m</math>用<math>p</math>进制表示，即<math>m=\sum_{i=0}^{k}m_ip^i</math> ，其中<math>k</math>''为非负整数''、<math>m_i</math>为整数且<math>0\leq m_i\leq p-1</math>。注意到
: <math>\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}</math>
其中<math>n_i</math>是<math>n</math>的<math>p</math>进制表达的第<math>i</math>位。此即证明了本定理。

== 变型和推广 ==
* 二项式系数 <math>\tbinom{m}{n}</math> 中含有质数<math>p</math>的幂次为算式<math>n</math>和<math>m-n</math>在<math>p</math>进制下进行相加计算的进位次数。(被称为[[庫默爾定理]].)
* Andrew Granville将卢卡斯定理由素数推广到了到素数的幂次<ref>{{Cite journal|title=Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers|author=[[Andrew Granville]]|url=http://www.dms.umontreal.ca/%7Eandrew/PDF/BinCoeff.pdf|journal=Canadian Mathematical Society Conference Proceedings|year=1997|volume=20|pages=253–275|mr=1483922|deadurl=yes|archiveurl=https://web.archive.org/web/20170202003812/http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf|archivedate=2017-02-02|access-date=2016-09-30}}</ref>。

== 参考资料==
{{Reflist}}

== 外部链接==
* {{PlanetMath|urlname=LucassTheorem|title=Lucas's Theorem}}
* [[arxiv:1301.4250|Alternate Proof of Lucas'Theorem]]

[[Category:素數]]