MENU

Proof of Lucas' theorem

2023 年 12 月 22 日 • 阅读: 1218 • 算法

The Theorem

对于非负整数 $n, m$ 和质数 $p$,有

$$ C_{n}^{m} \equiv C_{n_k}^{m_k} C_{n_{k -1}}^{m_{k - 1}} \cdots C_{n_0}^{m_0} \pmod p \tag{1} $$

其中,

$$ \begin{eqnarray} n = n_kp^k + n_{k - 1}p^{k - 1} + \cdots + n_1p + n_0 \tag{2} \\\ m = m_kp^k + m_{k - 1}p^{k - 1} + \cdots + m_1p + m_0 \tag{3} \end{eqnarray} $$

分别是 $n,m$ 的 $p$ 进制展开,$k$ 为非负整数,$0 \le n_i, m_i \le p - 1$。

Inference

由式 $(2), (3)$ 得

$$ \begin{eqnarray} n \bmod p = n_0 \tag{4} \\\ m \bmod p = m_0 \tag{5} \\\ \lfloor \frac{n}{p} \rfloor = n_kp^{k - 1} + n_{k - 1}p^{k - 2} + \cdots + n_1 \tag{6} \\\ \lfloor \frac{m}{p} \rfloor = m_kp^{k - 1} + m_{k - 1}p^{k - 2} + \cdots + m_1 \tag{7} \end{eqnarray} $$

将定理运用到式 $(6), (7)$ 上,有

$$ C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \equiv C_{n_k}^{m_k} C_{n_{k -1}}^{m_{k - 1}} \cdots C_{n_1}^{m_1} \pmod p \tag{8} $$

将式 $(4), (5), (8)$ 代入式 $(1)$ 得

$$ C_{n}^{m} \equiv C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} C_{n \bmod p}^{m \bmod p} \pmod p \tag{9} $$

The Proof

对于质数 $p$ 和整数 $k$,当 $1 \le k \le p - 1$ 时,有

$$ C_{p}^{k} = \frac{p \cdot (p - 1) \cdots (p - k + 1)}{k \cdot (k - 1) \cdots 1} \tag{10} $$

由于分母的每一项都与 $p$ 互质,因此 $C_{p}^{k} \bmod p = 0$。进而

$$ \begin{array} \left (1 + X)^p & = C_p^0 + C_p^1X + C_p^2X^2 + \cdots + C_p^{p - 1}X^{p - 1} + C_p^pX^p \\\ & \equiv 1 + X^p \pmod p \tag{11} \end{array} $$

下面用数学归纳法证明 $(1 + X)^{p^i} \equiv 1 + X^{p^i} \pmod p$ 对于任意正整数 $i$ 都成立。

  1. 已证 $i = 1$ 时,上式成立。
  2. 假设当 $i = k$ 时,上式成立,则当 $i = k + 1$ 时,

    $$ \begin{array} \left (1 + X)^{p^{k + 1}} &= [(1 + X)^{p^k}]^p \\\ &\equiv (1 + X^{p^k})^p \pmod p,\ 令 X^\prime = X^{p^k},运用式 (11) \\\ &\equiv 1 + (X^{p^k})^p \pmod p \\\ &\equiv 1 + X^{p^{k + 1}} \pmod p \tag{12} \end{array} $$

由此得证。进而

$$ \begin{array} \left (1 + X)^n & = (1 + X)^{n_kp^k + n_{k - 1}p^{k - 1} + \cdots + n_1p + n_0} \\\ & = (1 + X)^{n_kp^k} \cdot (1 + X)^{n_{k - 1}p^{k - 1}} \cdots (1 + X)^{n_{1}p} \cdot (1 + X)^{n_{0}} \\\ & \equiv (1 + X^{p^k})^{n_k} \cdot (1 + X^{p^{k - 1}})^{n_{k - 1}} \cdots (1 + X^p)^{n_{1}} \cdot (1 + X)^{n_{0}} \bmod p \tag{13} \end{array} $$

式 $(13)$ 的左边 $X^m$ 的系数为 $C_n^m$,结合式 $(3)$ 可验证右边 $X^m$ 的系数为

$$ C_{n_k}^{m_k} C_{n_{k -1}}^{m_{k - 1}} \cdots C_{n_1}^{m_1} C_{n_0}^{m_0} \tag{14} $$

由于左右两边系数一定相等,因此式 $(1)$ 成立。显然,当 $n < m$ 时,必存在 $n_i < m_i$,此时左右两边系数都为 $0$,等式仍然成立。

TG 大佬群 QQ 大佬群

返回文章列表 文章二维码
本页链接的二维码
打赏二维码
添加新评论

Loading captcha...

已有 1 条评论
  1. zizdog zizdog   Mac OS X 10.15.7  Safari 17.2.1

    好工整的笔记