インテジャーズ

インテジャーズ

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

pCrはpの倍数

高校生の皆さん! pが素数で、0 < r < p なる整数rに対して{}_pC_rは必ずpの倍数になります!!

え?そんなことは知ってるって??

そんなあなたのために、今日は第二種Stirling数ヴァージョンの類似の性質を紹介しましょう。なお、以下では二項係数はいつも通り\displaystyle \binom{n}{k}なる記号を用いることにします。

第二種Stirling数については

integers.hatenablog.com
mathtrain.jp

を参照してください。

目標は次の定理です*1

定理 pが素数、k1 < k < pを満たす整数であるならば、第二種Stirling数\displaystyle \left\{ {p \atop k} \right\}pで割り切れる。

第二種Stirling数の二項係数による表示を用います。

補題 非負整数n, k \ (k \leq n)に対し、
\displaystyle \left\{ {n \atop k} \right\} = \frac{1}{k!}\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^n
が成り立つ。

証明. nに関する数学的帰納法で証明する。n=(k=)0のときは両辺ともに1である。nのときに成り立つと仮定すると、

\begin{equation}\begin{split} \left\{ {n+1 \atop k} \right\} &= k\left\{ {n \atop k} \right\}+\left\{ {n \atop k-1} \right\} \\ &= \frac{k}{k!}\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^n + \frac{1}{(k-1)!}\sum_{j=0}^{k-1}(-1)^{k-1-j}\binom{k-1}{j}j^n \\ &= \frac{1}{(k-1)!}\sum_{j=0}^k(-1)^{k-j}\left\{ \binom{k}{j}-\binom{k-1}{j}\right\} j^n \\ &= \frac{1}{(k-1)!}\sum_{j=0}^k(-1)^{k-j}\binom{k-1}{j-1}j^n \\ &= \frac{1}{k!}\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^{n+1} \end{split}\end{equation}

n+1のときも成立することがわかる。 Q.E.D.

定理の証明. 二項展開の公式

\displaystyle (1-x)^k=\sum_{j=0}^k(-1)^j\binom{k}{j}{x^j}

を微分することにより

\displaystyle -k(1-x)^{k-1}=\sum_{j=0}^k(-1)^jj\binom{k}{j}x^{j-1}

が成り立つので、k > 1ならば

\displaystyle \sum_{j=0}^k(-1)^jj\binom{k}{j}=0

が成り立つ。よって、Fermatの小定理より

\displaystyle k! \left\{ {p \atop k} \right\} \equiv \sum_{j=0}^k(-1)^{k-j}j\binom{k}{j}=0 \pmod{p}

となって定理が成り立つことが分かる。 Q.E.D.

Bell数への応用

Bell数については

integers.hatenablog.com


を参照してください。素数pに対してB_p \equiv 2 \pmod{p}が常に成り立つことを今となっては簡単に確認できます。Bell数を第二種Stirling数を用いて表す公式により

\displaystyle B_p = \sum_{k=0}^{p}\left\{ {p \atop k} \right\}

が成り立ちますが、定理を適用することによって、

\displaystyle B_p \equiv \left\{ {p \atop 0} \right\} +\left\{ {p \atop 1} \right\} +\left\{ {p \atop p} \right\} = 0+1+1 = 2\pmod{p}

が得られます。

*1:定理、補題が出てきますが、それぞれ系、定理の方が相応しかったかもしれません。