Lucas定理

问题

已知质数 与自然数 。

求证

证明

首先先来看一个式子的取值：。

首先我们可以将式子展开：。

由于 是一个质数，所以我们知道 中恰好只含有一个 。

只有当 或 时才会含有一个 。

所以在 时 ，其他时候 。

再来看一个式子的取值：。

不妨暴力展开。 然后我们还知道： 其实是多项式 中， 的系数。

所以再来推一推： 显然，前面的一个括号中，只有 的项才有系数，后面的括号中，只有 的项中才有系数。

所以若 ，则 中的 个 ，必然有 个来自前面， 个来自后面。

所以 。