Bell数に関して最初に書いた記事
で紹介した興味深い合同式であるTouchardの合同式
Touchardの合同式 任意の非負整数と素数に対して、合同式が成立する。
の証明をいつか紹介すると約束していました。この記事で、Hurst-Schultzによるより強い主張
定理 任意の非負整数と素数に対して、合同式
を証明します。
補題1
証明. に対してはの倍数なので、
が成り立つ。最後にFermatの小定理およびを用いた。従って、Hurst-Schultzの定理
において、とすることによって
を得る。であるが、Hurst-Schultzの定理においてとすればなので、所望の合同式が成立することがわかった。 Q.E.D.
補題1によって、定理を証明するためには次の補題を証明すればよいことがわかります:
補題2 非負整数に対して合同式が成り立つ。
Hurst-Schultzはこの補題をBell数の定義に基づいて組合せ論的に証明しているのですが、補題1を繰り返し適用することによって帰納法で証明することもできます。
証明. に関する帰納法で証明する。よりのときはOK。のとき、すなわちはpCrはpの倍数 - INTEGERSで証明した。よって、としてのときに成り立つと仮定する*1。このとき、補題1および帰納法の仮定を繰り返し適用することによって、
となって、の場合も成立することが示された。 Q.E.D.
こうして、Bell数に関する美しい合同式を機械的に証明することができました。
*1:以下の論法ではのときはしか出ないので、帰納法のスタート地点としての場合を確認しておくことは必須である。