定義：$C_{n}^{m}\equiv?C_{n/p}^{m/p} * C_{n mod p}^{m mod p} (mod p)$

證明：1.由費(fèi)馬小定理可知$a^{p} \equiv p(mod p)$

? ? ? ? ? ?2.你需要知道二項式定理

? ? ? ? ? ?3.$\therefore (1+x)^{p} \equiv 1+x^{p} $——這個用前兩個東西證就好

? ? ? ? ? ?4.$\therefore (1+x)^{n}$

? ? ? ? ? ? ? $=(1+x)^{(n/p)*p}*(1+x)^{n mod p}$

? ? ? ? ? ? ? $\equiv (1+x^{p})^{n/p}*{1+x}^{n mod p}$

? ? ? ? ? ? ? $\equiv \sum\limits_{i=0}^{n/p} x^{pi} * \sum\limits_{j=0}^{n mod p} x^{j}$

? ? ? ? ? ? ? $\equiv?\sum\limits_{i=0}^{n/p} ?\sum\limits_{j=0}^{n mod p} x^{pi+j}$

? ? ? ? ? ? ? 當(dāng)我們?nèi)?x^{m}$這一項時，我們可以發(fā)現(xiàn)左邊根據(jù)二項式定理就是$C_{n}^{m}$,而右邊呢，$i=m/p$，$ j=m mod p $

? ? ? ? ? ? ??$\therefore C_{n}^{m}\equiv?C_{n/p}^{m/p} * C_{n mod p}^{m mod p} (mod p)$

?

? ? ? ? ?

? ? ?

轉(zhuǎn)載于:https://www.cnblogs.com/handsome-zlk/p/10567178.html

總結(jié)

以上是生活随笔為你收集整理的Lucas算法记录的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。