インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

Touchardの合同式

定理解説

Bell数に関して最初に書いた記事

integers.hatenablog.com


で紹介した興味深い合同式であるTouchardの合同式

Touchardの合同式 任意の非負整数nと素数pに対して、合同式
B_{n+p}\equiv B_n+B_{n+1} \pmod{p}
が成立する。

の証明をいつか紹介すると約束していました。この記事で、Hurst-Schultzによるより強い主張

定理 任意の非負整数n, mと素数pに対して、合同式
B_{n+p^m}\equiv mB_n+B_{n+1} \pmod{p}

を証明します。

補題1\ \ \ \displaystyle B_{n+p^m} \equiv (B_{p^m}-1)B_n+B_{n+1}\pmod{p}.

証明. 0 < r < p^mに対して\displaystyle \binom{p^m}{r}pの倍数なので、

\displaystyle \sum_{r=0}^{p^m}\binom{p^m}{r}B_{p^m-r}k^r \equiv B_{p^m}+k^{p^m}B_0 \equiv B_{p^m}+k\pmod{p}

が成り立つ。最後にFermatの小定理およびB_0=1を用いた。従って、

integers.hatenablog.com

で証明したHurst-Schultzの定理

\displaystyle B_{n+j}=\sum_{k=0}^n \left( \sum_{r=0}^j\binom{j}{r}B_{j-r}k^r \right) \left\{ {n \atop k} \right\}

において、j=p^mとすることによって

\displaystyle B_{n+p^m} \equiv \sum_{k=0}^n(B_{p^m}+k) \left\{ {n \atop k} \right\} = (B_{p^m}-1)\sum_{k=0}^n\left\{ {n \atop k} \right\} + \sum_{k=0}^n (1+k)\left\{ {n \atop k} \right\}\pmod{p}

を得る。\displaystyle B_n = \sum_{k=0}^n\left\{ {n \atop k} \right\}であるが、Hurst-Schultzの定理においてj=1とすれば\displaystyle B_{n+1} = \sum_{k=0}^n(1+k)\left\{ {n \atop k} \right\}なので、所望の合同式が成立することがわかった。 Q.E.D.

補題1によって、定理を証明するためには次の補題を証明すればよいことがわかります:

補題2 非負整数mに対して合同式
B_{p^m} \equiv m+1\pmod{p}
が成り立つ。

Hurst-Schultzはこの補題をBell数の定義に基づいて組合せ論的に証明しているのですが、補題1を繰り返し適用することによって帰納法で証明することもできます。

証明. mに関する帰納法で証明する。B_0=1よりm=0のときはOK。m=1のとき、すなわちB_p \equiv 2\pmod{p}

integers.hatenablog.com

で証明した。よって、m \geq 2としてm-1のときに成り立つと仮定する*1。このとき、補題1および帰納法の仮定を繰り返し適用することによって、

\begin{equation}\begin{split}B_{p^m} &= B_{(p-1)p^{m-1}+p^{m-1}} \\ &\equiv (B_{p^{m-1}}-1)B_{(p-1)p^{m-1}}+B_{(p-1)p^{m-1}+1} \\ &\equiv (m-1)B_{(p-1)p^{m-1}}+B_{(p-1)p^{m-1}+1} \\ &= (m-1)B_{(p-2)p^{m-1}+p^{m-1}}+B_{(p-2)p^{m-1}+1+p^{m-1}} \\ &\equiv (m-1)\left\{ (B_{p^{m-1}}-1)B_{(p-2)p^{m-1}}+B_{(p-2)p^{m-1}+1} \right\} \\ &\hspace{5mm} + (B_{p^{m-1}}-1)B_{(p-2)p^{m-1}+1}+B_{(p-2)p^{m-1}+2} \\ &\equiv (m-1)^2B_{(p-2)p^{m-1}}+2(m-1)B_{(p-2)p^{m-1}+1}+B_{(p-2)p^{m-1}+2} \\ &\equiv \cdots \\ &\equiv \sum_{k=0}^p\binom{p}{k}(m-1)^{p-k}B_k \\ &\equiv (m-1)^p + B_p \\ &\equiv (m-1)+2 = m+1 \pmod{p}\end{split}\end{equation}

となって、mの場合も成立することが示された。 Q.E.D.

こうして、Bell数に関する美しい合同式を機械的に証明することができました。

*1:以下の論法ではm=1のときはB_p \equiv B_p\pmod{p}しか出ないので、帰納法のスタート地点としてm=1の場合を確認しておくことは必須である。