二項係数と素数の剰余の関係
はじめに
こんにちは．きたせんです．先日数学で，ある組み合わせに関する公式を繰り返し用いると興味深い(？)結果が得られることに気づいたのでここに共有します．
その数式とはこちらです．
$ {}_n \mathrm{C}_r={}_{n-1}\mathrm{C}_{r-1}+{}_{n-1}\mathrm{C}_{r} \qquad(n,~r\in\mathbb{Z},~0\leqq r\leqq n)$
\begin{aligned}
(\text{右辺})&=\frac{(n-1)!}{(n-r)!(r-1)!}+\frac{(n-1)!}{(n-r-1)!r!}\\
&=\frac{r(n-1)!}{(n-r)!r!}+\frac{(n-r)(n-1)!}{(n-r)!r!}\\
&=\frac{n!}{(n-r)!r!}={}_{n}\mathrm{C}_{r}~//
\end{aligned}
※補足
$ {}_{n}\mathrm{C}_{r}$の組み合わせの中で特定の1個を含まない組み合わせ
→選ぶ個数は同じだが選べる対象は一つ減るから${}_{n-1}\mathrm{C}_{r} $
${}_{n}\mathrm{C}_{r}$の組み合わせの中で特定の1個を含む組み合わせ
→選ぶ残りの個数，選べる対象はともに1減るから${}_{n-1}\mathrm{C}_{r-1} $
両者は互いに排反であるから，和は${}_{n}\mathrm{C}_{r}$
というように意味づけをして証明することもできる．
補題を繰り返し用いる
では，この補題1を繰り返し用いるとどうなるのでしょうか？順番に実験して規則性を見出していきます．
\begin{cases}
{}_{n-1}\mathrm{C}_{r-1}&={}_{n-2}\mathrm{C}_{r-2}+{}_{n-2}\mathrm{C}_{r-1}\\
{}_{n-1}\mathrm{C}_{r}&={}_{n-2}\mathrm{C}_{r-1}+{}_{n-2}\mathrm{C}_{r}
\end{cases}
ですから，辺々足し合わせることにより，次の式を得ます．
${}_{n}\mathrm{C}_{r}={}_{n-2}\mathrm{C}_{r-2}+2{}_{n-2}\mathrm{C}_{r-1}+{}_{n-2}\mathrm{C}_{r}$
そして，補題1を用いて上式を書き下していくと，
\begin{cases}
{}_{n-2}\mathrm{C}_{r-2}&={}_{n-3}\mathrm{C}_{r-3}+{}_{n-3}\mathrm{C}_{r-2}\\
2{}_{n-2}\mathrm{C}_{r-1}&=2{}_{n-3}\mathrm{C}_{r-2}+2{}_{n-3}\mathrm{C}_{r-1}\\
{}_{n-2}\mathrm{C}_{r}&={}_{n-3}\mathrm{C}_{r-1}+{}_{n-3}\mathrm{C}_{r}
\end{cases}
ですから，辺々足し合せることにより，次の式を得ます．
${}_{n}\mathrm{C}_{r}={}_{n-3}\mathrm{C}_{r-3}+3{}_{n-3}\mathrm{C}_{r-2}+3{}_{n-3}\mathrm{C}_{r-1}+{}_{n}\mathrm{C}_{r}$
ここでもう規則性に気づいた人は天才かもしれません．さらに，補題1を用いて上式を書き下すと，
\begin{cases}
{}_{n-3}\mathrm{C}_{r-3}&={}_{n-4}\mathrm{C}_{r-4}+{}_{n-4}\mathrm{C}_{r-3}\\
3{}_{n-3}\mathrm{C}_{r-2}&=3{}_{n-4}\mathrm{C}_{r-3}+3{}_{n-4}\mathrm{C}_{r-2}\\
3{}_{n-3}\mathrm{C}_{r-1}&=3{}_{n-4}\mathrm{C}_{r-2}+3{}_{n-4}\mathrm{C}_{r-1}\\
{}_{n-3}\mathrm{C}_{r}&={}_{n-4}\mathrm{C}_{r-1}+{}_{n-4}\mathrm{C}_{r}
\end{cases}
ですから，辺々足し合わせることにより，次の式を得ます．
${}_{n}\mathrm{C}_{r}={}_{n-4}\mathrm{C}_{r-4}+4{}_{n-4}\mathrm{C}_{r-3}+6{}_{n-4}\mathrm{C}_{r-2}+4{}_{n-4}\mathrm{C}_{r-1}+{}_{n-4}\mathrm{C}_{r}$
もう気づいたでしょう．そう，展開した右辺の各項の係数も二項係数になっています！！
ここから，次の予想を立てることができます．
すべての$p\in\mathbb{N}$について，$\displaystyle {}_{n}\mathrm{C}_{r}=\sum_{k=0}^{p}{}_{p}\mathrm{C}_{k}\cdot{}_{n-p}\mathrm{C}_{r-k}~$とかける．
いかにも数学的帰納法で証明できそうな内容ですね($p$が変数なの気持ち悪くてごめんなさい)．証明は少し煩雑に思えるかもしれません．ですが，証明の段取りは上で行った実験から見えているはずです！
二項係数の級数表示を証明してみよう
$p$に関する数学的帰納法で証明する．
$p=1$のとき
$\displaystyle (\text{右辺})=\sum_{k=0}^{1}{}_{1}\mathrm{C}_{k}\cdot {}_{n-1}\mathrm{C}_{r-k}={}_{n-1}\mathrm{C}_{r}+{}_{n-1}\mathrm{C}_{r-1}={}_{n}\mathrm{C}_{r}\quad(\because \text{補題1})$
より成立する．$p=l~(l\geqq 1)$のとき
$\displaystyle {}_{n}\mathrm{C}_{r}=\sum_{k=0}^{l}{}_{l}\mathrm{C}_{k}\cdot {}_{n-l}\mathrm{C}_{r-k}~$とかけることを仮定する．
$p=l+1$の場合について考える．
${}_{l}\mathrm{C}_{k}\cdot {}_{n-l}\mathrm{C}_{r-k}={}_{l}\mathrm{C}_{k}({}_{n-l-1}\mathrm{C}_{r-k-1}+{}_{n-l-1}\mathrm{C}_{r-k})\quad(\because\text{補題1})$とかけるから，$k$を$0$から$l$まで動かして足し合わせれば，$p=l$の場合の級数表示(仮定)となる．式を書き下すと，
\begin{aligned}
{}_{l}\mathrm{C}_{0}\cdot {}_{n-l}\mathrm{C}_{r}&={}_{l}\mathrm{C}_{0}\cdot{}_{n-l-1}\mathrm{C}_{r-1}+{}_{l}\mathrm{C}_{0}\cdot{}_{n-l-1}\mathrm{C}_{r}\\
+\\
{}_{l}\mathrm{C}_{1}\cdot {}_{n-l}\mathrm{C}_{r-1}&={}_{l}\mathrm{C}_{1}\cdot{}_{n-l-1}\mathrm{C}_{r-2}+{}_{l}\mathrm{C}_{1}\cdot{}_{n-l-1}\mathrm{C}_{r-1}\\
+\\
{}_{l}\mathrm{C}_{2}\cdot {}_{n-l}\mathrm{C}_{r-2}&={}_{l}\mathrm{C}_{2}\cdot{}_{n-l-1}\mathrm{C}_{r-3}+{}_{l}\mathrm{C}_{2}\cdot{}_{n-l-1}\mathrm{C}_{r-2}\\
+\\
\vdots\\
+\\
{}_{l}\mathrm{C}_{k}\cdot {}_{n-l}\mathrm{C}_{r-k}&={}_{l}\mathrm{C}_{k}\cdot{}_{n-l-1}\mathrm{C}_{r-k-1}+{}_{l}\mathrm{C}_{k}\cdot{}_{n-l-1}\mathrm{C}_{r-k}\\
+\\
{}_{l}\mathrm{C}_{k+1}\cdot {}_{n-l}\mathrm{C}_{r-k-1}&={}_{l}\mathrm{C}_{k+1}\cdot{}_{n-l-1}\mathrm{C}_{r-k-2}+{}_{l}\mathrm{C}_{k+1}\cdot{}_{n-l-1}\mathrm{C}_{r-k-1}\\
+\\
\vdots\\
+\\
{}_{l}\mathrm{C}_{l-1}\cdot {}_{n-l}\mathrm{C}_{r-l+1}&={}_{l}\mathrm{C}_{l-1}\cdot{}_{n-l-1}\mathrm{C}_{r-l}+{}_{l}\mathrm{C}_{l-1}\cdot{}_{n-l-1}\mathrm{C}_{r-l+1}\\
+\\
{}_{l}\mathrm{C}_{l}\cdot {}_{n-l}\mathrm{C}_{r-l}&={}_{l}\mathrm{C}_{l}\cdot{}_{n-l-1}\mathrm{C}_{r-l-1}+{}_{l}\mathrm{C}_{l}\cdot{}_{n-l-1}\mathrm{C}_{r-l}\\
\end{aligned}
(※上式の左辺を足し合わせていくと，$p=l$の場合の級数表示$\displaystyle \sum_{k=0}^{l}{}_{l}\mathrm{C}_{k}\cdot{}_{n-l}\mathrm{C}_{r-k}$)
右辺について，補題1から導かれる，${}_{l}\mathrm{C}_{k}+{}_{l}\mathrm{C}_{k+1}={}_{l+1}\mathrm{C}_{k+1}$という関係に注意してその和を計算すると，
\begin{aligned}
(\text{右辺の和})=&{}_{l}\mathrm{C}_{0}\cdot{}_{n-l-1}\mathrm{C}_{r}\\
&+({}_{l}\mathrm{C}_{0}+{}_{l}\mathrm{C}_{1}){}_{n-l-1}\mathrm{C}_{r-1}\\
&+({}_{l}\mathrm{C}_{1}+{}_{l}\mathrm{C}_{2}){}_{n-l-1}\mathrm{C}_{r-2}\\
&+({}_{l}\mathrm{C}_{2}+{}_{l}\mathrm{C}_{3}){}_{n-l-1}\mathrm{C}_{r-3}\\
\vdots\\
&+({}_{l}\mathrm{C}_{k}+{}_{l}\mathrm{C}_{k+1}){}_{n-l-1}\mathrm{C}_{r-k-1}\\
&+({}_{l}\mathrm{C}_{k+1}+{}_{l}\mathrm{C}_{k+2}){}_{n-l-1}\mathrm{C}_{r-k-2}\\
\vdots\\
&+({}_{l}\mathrm{C}_{l-2}+{}_{l}\mathrm{C}_{l-1}){}_{n-l-1}\mathrm{C}_{r-l+1}\\
&+({}_{l}\mathrm{C}_{l-1}+{}_{l}\mathrm{C}_{l}){}_{n-l-1}\mathrm{C}_{r-l}\\
&+{}_{l}\mathrm{C}_{l}\cdot{}_{n-l-1}\mathrm{C}_{r-l-1}\\
\\
=&{}_{l+1}\mathrm{C}_{0}\cdot{}_{n-l-1}\mathrm{C}_{r}\qquad(\because {}_{l}\mathrm{C}_{0}={}_{l+1}\mathrm{C}_{0}=1)\\
&+{}_{l+1}\mathrm{C}_{1}\cdot{}_{n-l-1}\mathrm{C}_{r-1}\\
&+{}_{l+1}\mathrm{C}_{2}\cdot{}_{n-l-1}\mathrm{C}_{r-2}\\
&+{}_{l+1}\mathrm{C}_{3}\cdot{}_{n-l-1}\mathrm{C}_{r-3}\\
\vdots\\
&+{}_{l+1}\mathrm{C}_{k+1}\cdot{}_{n-l-1}\mathrm{C}_{r-k-1}\\
&+{}_{l+1}\mathrm{C}_{k+2}\cdot{}_{n-l-1}\mathrm{C}_{r-k-2}\\
\vdots\\
&+{}_{l+1}\mathrm{C}_{l-1}\cdot{}_{n-l-1}\mathrm{C}_{r-l+1}\\
&+{}_{l+1}\mathrm{C}_{l}\cdot{}_{n-l-1}\mathrm{C}_{r-l}\\
&+{}_{l+1}\mathrm{C}_{l+1}\cdot{}_{n-l-1}\mathrm{C}_{r-l-1}\qquad(\because {}_{l}\mathrm{C}_{l}={}_{l+1}\mathrm{C}_{l+1}=1)\\
\\
=&\sum_{k=0}^{l+1}{}_{l+1}\mathrm{C}_{k}\cdot{}_{n-l-1}\mathrm{C}_{r-k}
\end{aligned}
したがって，$\displaystyle (\text{左辺の和})=(\text{右辺の和})\iff \sum_{k=0}^{l}{}_{l}\mathrm{C}_{k}\cdot{}_{n-l}\mathrm{C}_{r-k}=\sum_{k=0}^{l+1}{}_{l+1}\mathrm{C}_{k}\cdot{}_{n-l-1}\mathrm{C}_{r-k} $
が成り立ち，仮定から，$p=l+1$のときも$\displaystyle {}_{n}\mathrm{C}_{r}=\sum_{k=0}^{l+1}{}_{l+1}\mathrm{C}_{k}\cdot{}_{n-l-1}\mathrm{C}_{r-k}$とかけるため，数学的帰納法によって，題意は示される．//
二項係数の級数表示の応用
この級数表示の何が嬉しいかを次に解説していきます．
$p$を素数とするとき，$1\leqq k\leqq p-1$を満たす$k\in\mathbb{N}$に対して，二項係数${}_{p}\mathrm{C}_{k}$は$p$の倍数である．
$\displaystyle {}_{p}\mathrm{C}_{k}=\frac{p!}{(p-k)!k!}=\frac{p}{k}\cdot\frac{(p-1)!}{(p-k)!(k-1)!}=\frac{p}{k}\cdot{}_{p-k}\mathrm{C}_{k-1}$
であるから，$k\cdot{}_{p}\mathrm{C}_{k}=p\cdot {}_{p-1}\mathrm{C}_{k-1}$が成り立つ．左辺が$p$の倍数でかつ$p,~k$は互いに素であるから，${}_{p}\mathrm{C}_{k}$は$p$の倍数となる．//
ここで，先ほど証明した二項係数の級数表示，$\displaystyle {}_{n}\mathrm{C}_{r}=\sum_{k=0}^{p}{}_{p}\mathrm{C}_{k}\cdot{}_{n-p}\mathrm{C}_{r-k}$をながめると，新たな知見が得られると思います．$\sum$で足し合わせられる項のうち，$1\leqq k\leqq p-1$を満たすものについては，補題2から，$p$の倍数です．ここから，以下の公式が導けます．
$p$が素数ならば，${}_{n}\mathrm{C}_{r}\equiv {}_{n-p}\mathrm{C}_{r}+{}_{n-p}\mathrm{C}_{r-p}~(\mathrm{mod}~p)\qquad(0\leqq p\leqq r\leqq n)$
\begin{aligned} {}_{n}\mathrm{C}_{r}&=\sum_{k=0}^{p}{}_{p}\mathrm{C}_{k}\cdot{}_{n-p}\mathrm{C}_{r-k}\\ &={}_{p}\mathrm{C}_{0}\cdot{}_{n-p}\mathrm{C}_{r}+\underbrace{\sum_{k=1}^{p-1}{}_{p}\mathrm{C}_{k}\cdot{}_{n-p}\mathrm{C}_{r-k}}_{p\text{の倍数}}+{}_{p}\mathrm{C}_{p}\cdot{}_{n-p}\mathrm{C}_{r-p}\\ &\equiv {}_{n-p}\mathrm{C}_{r}+{}_{n-p}\mathrm{C}_{r-p}~(\mathrm{mod}~p)// \end{aligned}
なんと，$p$を法とする剰余類で二項係数を取り扱うときに使いやすそうな式を得ることができました！
式の見た目も何やら補題1に似たものがあります...ですので，繰り返しこれを用いるとまた同様の結果が得られそうな予感がします．
また繰り返し用いてみよう
以下，法はすべて$(\mathrm{mod}~p)$とします．
\begin{cases}
{}_{n-p}\mathrm{C}_{r-p}&\equiv{}_{n-2p}\mathrm{C}_{r-2p}+{}_{n-2p}\mathrm{C}_{r-p}\\
{}_{n-p}\mathrm{C}_{r}&\equiv{}_{n-2p}\mathrm{C}_{r-p}+{}_{n-2p}\mathrm{C}_{r}
\end{cases}
ですから，辺々足し合わせることにより，次の式を得ます．
${}_{n}\mathrm{C}_{r}\equiv{}_{n-2p}\mathrm{C}_{r-2p}+2{}_{n-2p}\mathrm{C}_{r-p}+{}_{n-2p}\mathrm{C}_{r}$
そして，公式1を用いて上式を書き下していくと，
\begin{cases}
{}_{n-2p}\mathrm{C}_{r-2p}&\equiv{}_{n-3p}\mathrm{C}_{r-3p}+{}_{n-3p}\mathrm{C}_{r-2p}\\
2{}_{n-2p}\mathrm{C}_{r-p}&\equiv2{}_{n-3p}\mathrm{C}_{r-2p}+2{}_{n-3p}\mathrm{C}_{r-p}\\
{}_{n-2p}\mathrm{C}_{r}&\equiv{}_{n-3p}\mathrm{C}_{r-p}+{}_{n-3p}\mathrm{C}_{r}
\end{cases}
ですから，辺々足し合せることにより，次の式を得ます．
${}_{n}\mathrm{C}_{r}\equiv{}_{n-3p}\mathrm{C}_{r-3p}+3{}_{n-3p}\mathrm{C}_{r-2p}+3{}_{n-3p}\mathrm{C}_{r-p}+{}_{n}\mathrm{C}_{r}$
なんだか既視感を感じませんか？記事の最初の方で二項係数の級数表示を導くにあたって実験をしましたが，それを(ほぼ)同じですね．したがって，次の補題が導けます．
すべての自然数$m$について，$\displaystyle {}_{n}\mathrm{C}_{r}\equiv \sum_{k=0}^{m}{}_{m}\mathrm{C}_{k}\cdot{}_{n-mp}\mathrm{C}_{r-kp}~(\mathrm{mod}~p)$
二項係数の級数表示${}_{n}\mathrm{C}_{r}=\displaystyle \sum_{k=0}^{m}{}_{m}\mathrm{C}_{k}\cdot{}_{n-m}\mathrm{C}_{r-k}$において，${}_{n-m}\mathrm{C}_{r-k}\mapsto {}_{n-mp}\mathrm{C}_{r-kp}$とすれば，繰り返しのアルゴリズムがほぼ同じであることから容易に示される．//
では，$m=p$であるとき，どうなるでしょうか？このとき，${}_{p}\mathrm{C}_{k}$は，$0\leqq k\leqq p-1$において，補題2から$p$の倍数です．したがって，次の公式が導けます．
$p$が素数ならば，${}_{n}\mathrm{C}_{r}\equiv {}_{n-p^2}\mathrm{C}_{r}+{}_{n-p^2}\mathrm{C}_{r-p^2}~(\mathrm{mod}~p)$
補題3について，$m=p$のとき，
\begin{aligned}
{}_{n}\mathrm{C}_{r}&\equiv\sum_{k=0}^{p}{}_{p}\mathrm{C}_{k}\cdot{}_{n-p^2}\mathrm{C}_{r-kp}\\
&={}_{p}\mathrm{C}_{0}\cdot{}_{n-p^2}\mathrm{C}_{r}+\underbrace{\sum_{k=1}^{p-1}{}_{p}\mathrm{C}_{k}\cdot{}_{n-p^2}\mathrm{C}_{r-kp}}_{p\text{の倍数}}+{}_{p}\mathrm{C}_{p}\cdot{}_{n-p^2}\mathrm{C}_{r-p^2}\\
&\equiv {}_{n-p^2}\mathrm{C}_{r}+{}_{n-p^2}\mathrm{C}_{r-p^2}~(\mathrm{mod}~p)//
\end{aligned}
どうやらまた規則性が見えてきました...次の命題が成り立つことを予想できそうです．
二項係数と素数の剰余の関係を一般化してみよう
$p$が素数ならば，任意の$q\in\mathbb{N}$について，${}_{n}\mathrm{C}_{r}\equiv {}_{n-p^q}\mathrm{C}_{r}+{}_{n-p^q}\mathrm{C}_{r-p^q}~(\mathrm{mod}~p)$
またもや数学的帰納法で示せそうな内容ですね．筆者も何回も同じようなことを書いていて疲れたので少し証明は手を抜かせてください...
$q$に関する数学的帰納法で示す．
- $q=1$のとき
公式1から成立． - $q=l~(l\geqq1)$のとき
$ {}_{n}\mathrm{C}_{r}\equiv{}_{n-p^l}\mathrm{C}_{r}+{}_{n-p^l}\mathrm{C}_{r-p^l}~(\mathrm{mod}~p) $を仮定する．
$q=l+1$のときを考える．
補題3と同じようなやり方，アルゴリズムを用いることで，すべての自然数$m$について，$\displaystyle {}_{n}\mathrm{C}_{r}\equiv \sum_{k=0}^{m}{}_{m}\mathrm{C}_{k}\cdot{}_{n-mp^l}\mathrm{C}_{r-kp^l}~(\mathrm{mod}~p)$が成り立つ．ここにおいて，$m=p$のとき，公式2の証明の仮定のようにすることで，
\begin{aligned}
{}_{n}\mathrm{C}_{r}&\equiv\sum_{k=0}^{p}{}_{p}\mathrm{C}_{k}\cdot{}_{n-p^{l+1}}\mathrm{C}_{r-kp^l}\\
&={}_{p}\mathrm{C}_{0}\cdot{}_{n-p^{l+1}}\mathrm{C}_{r}+\underbrace{\sum_{k=1}^{p-1}{}_{p}\mathrm{C}_{k}\cdot{}_{n-p^l}\mathrm{C}_{r-kp^l}}_{p\text{の倍数}}+{}_{p}\mathrm{C}_{p}\cdot{}_{n-p^{l+1}}\mathrm{C}_{r-p^{l+1}}\\
&\equiv {}_{n-p^{l+1}}\mathrm{C}_{r}+{}_{n-p^{l+1}}\mathrm{C}_{r-p^{l+1}}~(\mathrm{mod}~p)
\end{aligned}
$q=l+1$のときも成り立つことがわかる．したがって，数学的帰納法から，題意が示される．//
具体的な公式の活用
${}_{100}\mathrm{C}_{50} $の$1$の位を求めよ．
解答
まずは，${}_{100}\mathrm{C}_{50} $を$5$で割った余りを考えればよい．法は$(\mathrm{mod}~5)$とする．公式2を繰り返し用いると，
\begin{aligned}
{}_{100}\mathrm{C}_{50}&\equiv{}_{100-5^2}\mathrm{C}_{50}+{}_{100-5^2}\mathrm{C}_{50-5^2}\\
&={}_{75}\mathrm{C}_{50}+{}_{75}\mathrm{C}_{25}=2{}_{75}\mathrm{C}_{25}\\
&\equiv 2({}_{75-5^2}\mathrm{C}_{25}+{}_{75-5^2}\mathrm{C}_{25-5^2})\\
&=2{}_{50}\mathrm{C}_{25}+2{}_{50}\mathrm{C}_{0}\\
&\equiv2({}_{50-5^2}\mathrm{C}_{25}+{}_{50-5^2}\mathrm{C}_{25-5^2})+2\\
&\equiv2{}_{25}\mathrm{C}_{25}+2{}_{25}\mathrm{C}_{0}+2=6\\
&\equiv 1~(\mathrm{mod}~5)
\end{aligned}
さらに，${}_{100}\mathrm{C}_{50} $を2で割った余りを考えると，法を$(\mathrm{mod}~2)$として，公式1から，
\begin{aligned}
{}_{100}\mathrm{C}_{50}&\equiv {}_{100-2}\mathrm{C}_{50}+{}_{100-2}\mathrm{C}_{50-2}\\
&={}_{98}\mathrm{C}_{50}+{}_{98}\mathrm{C}_{48}\\
&= 2{}_{98}\mathrm{C}_{48}\\
&\equiv 0~(\mathrm{mod} 2)
\end{aligned}
したがって，${}_{100}\mathrm{C}_{50}$は$5$で割って$1$余るような偶数である．したがって，${}_{100}\mathrm{C}_{50}$を$10$で割った余りは$6$となる．であるから，${}_{100}\mathrm{C}_{50}$の$1$の位は$6$となる．
おわりに
今回がMathlogの初投稿です！色々タイプミス等もあるかもしれませんが，何卒よろしくお願いします＞＜
今回の剰余の関係については，素数にしか使えないのが少し残念かな...と感じております．
何かミス等あればコメントなどでお知らせください．加筆修正をします．ではまた．