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}$

を証明します。

補題１ $\ \ \ \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$ を用いた。従って、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.

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

補題２ 非負整数 $m$ に対して合同式

$B_{p^m} \equiv m+1\pmod{p}$

が成り立つ。

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

証明. $m$ に関する帰納法で証明する。 $B_0=1$ より $m=0$ のときはOK。 $m=1$ のとき、すなわち $B_p \equiv 2\pmod{p}$ はpCrはpの倍数 - INTEGERSで証明した。よって、 $m \geq 2$ として $m-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}$