組み合わせ数の合同式 - 数学大好き宣言！

f:id:mochi-mochi61:20211213045042p:plain
pを素数とする。
この記事では、a≡b でa≡b(mod p) を表すこととする。
(定理)a,bを自然数、a＞bとする。次が成り立つ。 $\dbinom{pa}{pb}≡\dbinom{a}{b}$
ただし、 $\binom{a}{b}$ は二項係数 ( ${}_a C_b$ と同じ)。

証明:
$\displaystyle\dbinom{pa}{pb}=\prod_{k=0}^{pb-1} \frac{p a- k}{p b- k}$
$=\displaystyle\prod_{\alpha=0}^{p-1} \prod_{t=0}^{b-1}\frac{p a-(\alpha+p t)}{p b-(\alpha+p t)}$
ここで、 $p a-(\alpha+p t)\equiv-\alpha, p b-(\alpha+p t) \equiv-\alpha$ だから、
α≢0 のとき、 $\frac{p b-(\alpha+p t)}{p a-(\alpha+p t)}\equiv 1$
また、
$\displaystyle\prod_{t=0}^{b-1} \frac{p b-p t}{p a-p t}=\prod_{t=0}^{p-1} \frac{a-t}{b-t}=\binom{a}{b}.$

よって $\dbinom{pa}{pb}≡\dbinom{a}{b}$ .