Lucas定理证明

描述：

当为大数，为素数时，Lucas定理是用来求 的值。适用领域范围：在数论中求大组合数取模。

通式：

为素数

证明:

已知为素数,将非负整数转化成进制数:

由于p是素数对于 ,都有

由二项式定理：

由上面的推理可得：

即： ①

设：

代入公式①得:

对 和分别使用二项展开式

即: ②

对进行二项式展开：

③

首先求③中的的系数为

再求②中的我们发现，当且仅当能够得到的系数，即为：

即：

即：

即：