（1）Lucas定理：p為素數，則有:
（2）證明： n=(ak...a2,a1,a0)p = (ak...a2,a1)p*p + a0 = [n/p]*p+a0，m=[m/p]*p+b0其次，我們知道，對任意質數p有(1+x)^p=1+(x^p)(mod p) 。我們隻要證明這個式子：C(n,m)=C([n/p],[m/p]) * C(a0,b0)(mod p)，那麼就可以用歸納法證明整個定理。對于模p而言，我們有下面的式子成立：
上式左右兩邊的x的某項x^m(m<=n)的系數對模p同餘。其中左邊的x^m的系數是 C(n,m)。 而由于a0和b0都小于p，是以右邊的x^m 一定是由 x^([m/p]*p) 和 x^b0 (即i=[m/p] , j=b0 ) 相乘而得 是以有：C(n,m)=C([n/p],[m/p]) * C(a0,b0) (mod p)。
（3）拓展應用：上面的p是素數，那麼不是素數怎麼辦呢？若不是素數，将p分解質因數，将C(n,m)分别按照（1）中的方法求對p的質因數的模，然後用中國剩餘定理合并。比如計算C(10,3)%14。C(10,3)=120,14有兩個質因數2和7，120%2=0,120%7=1,這樣用(2,0)(7,1)找到最小的正整數8即是答案，即C(10,3)%14=8。注意，這裡隻适用于p分解完質因數後每個質因數隻出現一次，例如12=2*2*3就不行，因為2出現了兩次。若p分解完質因數後，含有某個質因數出現多次，比如C(10,3)%98,其中98=2*7*7,此時就要把7*7看做一個數,即:120%2=0,120%49=22,用(2,0)(49,22)和中國剩餘定理得到答案22，即C(10,3)%98=22。此時，你又會有疑問，C(10,3)%49不也是模一個非素數嗎？此時不同的是這個非素數不是一般的非素數，而是某個素數的某次方。下面（4）介紹如何計算C(n,m)%p^t(t>=2,p為素數)。
（4）計算C(n,m)%p^t。我們知道，C(n,m)=n!/m!/(n-m)!，若我們可以計算出n!%p^t，我們就能計算出m!%p^t以及(n-m)!%p^t。我們不妨設x=n!%p^t,y=m!%p^t,z=(n-m)!%p^t,那麼答案就是x*reverse(y,p^t)*reverse(z,p^t)(reverse(a,b)計算a對b的乘法逆元)。那麼下面問題就轉化成如何計算n!%p^t。比如p=3,t=2,n=19,
n!=1*2*3*4*5*6*7*8* ……*19
=[1*2*4*5*7*8*… *16*17*19]*(3*6*9*12*15*18)
=[1*2*4*5*7*8*… *16*17*19]*3^6(1*2*3*4*5*6)
然後發現後面的是(n/p)!，于是遞歸即可。前半部分是以p^t為周期的[1*2*4*5*7*8]=[10*11*13*14*16*17](mod 9)。下面是孤立的19，可以知道孤立出來的長度不超過 p^t,于是暴力即可。那麼最後剩下的3^6啊這些數怎麼辦呢？我們隻要計算出n!,m!,(n-m)!裡含有多少個p(不妨設a,b,c)，那麼a-b-c就是C(n,m)中p的個數，直接算一下就行。
至此整個計算C(n,m)%p(p為任意數)的問題完美解決。下面給出代碼：