mod逆元を用いたCombination計算の証明

1. 用いる道具

1-1. モジュラ逆元

定義
モジュラ逆元 $x$ とは、
$\ a,\ m \in \bf Z$ について、 $ax \equiv 1(mod \ m)を満たす整数xであり$
$a^{-1} \equiv x(mod\ m)$
と表記する。

1-2. フェルマーの小定理

条件
$a\in \bf Z , \ p \in prime\ number$
$a$ と $p$ は互いに素 $\Leftrightarrow a\not \equiv0(mod \ p)$
フェルマーの小定理
$a^p \equiv 1 (mod \ p)$
補題
フェルマーの小定理より、
$a^{p-1}a \equiv 1 (mod \ p)$
$a^{-1} \equiv a^{p-1}$

2. Combinationの余り

${}_n C_k = \frac{n!}{k!(n-k)!}\\ \Leftrightarrow k!(n-k)!{}_nC_k = n!\\$
この式について $p\in \bf Z$ を法とした合同式を書くと、
$k!(n-k)!{}_nC_k \equiv n!\\ \Leftrightarrow ((k!)^{-1}k!)(n-k)!{}_nC_k \equiv n! (k!)^{-1}\\ \Leftrightarrow (n-k)!{}_nC_k \equiv n! (k!)^{-1}\\ \Leftrightarrow {}_nC_k \equiv n! (k!)^{-1}((n-k)!)^{-1}$
合同式の積の結合法則を用いた。ここで、 $p$ が素数のとき、上述した補題から
$(k!)^{-1} \equiv (k!)^{p-2}$
$((n-k)!)^{-1} \equiv ((n-k)!)^{p-2}$
を代入すると、