文章目录
Lucas定理:C(n,m)=C(n/p,m/p)\*C(n%p,m%p)(以下p均为素数,/为下取整),a=n%p,b=m%p。
证明:有C(p,n)%p=0(n>0&&n<p)。
因为C(p,n)=p!/n!/(n-p)!,p为素数,不可能被消去。
然后有(1+x)^p=1+x^p(%p)。
因为展开后每一项的系数为C(p,i),由C(p,n)%p=0得在%p下均为0。
然后有(1+x)^n=(1+x)^(n/p\*p)\*(1+x)^(n%p)                                         
             =(1+x^p)^(n/p)\*(1+x)^(n%p)(%p下)                                 
             =[x^p\*sum(C(n/p,i))x^i]\*[sum(C(n%p,j))\*x^j](i=1..n/p,j=0..n%p)     
而(1+x)^n=sum(C(n,i)\*(x^i))(i=1..n)                                         
上式左右两边x的某项x^m的系数对p同余,其中左边x^m的系数是C(n,m),因为a,b都小于p,
因此右边的x^m肯定是由x^(m/p\*p)和x^b和(i=m/p,j=b)相乘得到。
如何说明每一项一一对应?考虑到x的值可以任意取,在无数种不同的取值下x^i的值也会改变,而式子始终成立,因此一定一一对应。 
文章目录