n! と mCn を素数 p で割り切れる回数（改訂版）

　かなり初期に $n!$ や $_m C^n$ を素数 $p$ で割り切れる回数について書いたのですが、かなり気に入ってるのでもう少し読みやすくできないかと思い、改めて紹介します。以下のことは認めることにしてください。

任意の素数 $p$ 、自然数 $n$ について、 $p^m \leq n \leq p^{m+1}-1$ ならば、

ある自然数 $a_k \, (k=0,1,2,\cdots , m; \, 0 \leq a_k \leq p-1)$ が存在して

$n=a_0 p^0 + a_1 p^1 + a_2 p^2 + \cdots + a_mp^m$ を満たす。

　さて、上の n について $n!$ を素数 $p$ で割り切れる回数 $v_p(n!)$ を求めるには、 $n!$ を $p, p^2, p^3, \cdots , p^m$ でそれぞれ割った商の総和を求めればよかったです。これを式で表すと次のようになります。

$v_p(n!)={\displaystyle \sum_{l=1}^m \lfloor \frac{n}{p^l} \rfloor }$

　しかし、このままでは $\sum$ の計算ができないので、 $\lfloor \frac{n}{p^l} \rfloor$ を何とか床関数を使わずに表せないか考えます。ここで $n=a_0 p^0 + a_1 p^1 + a_2 p^2 + \cdots + a_mp^m$ が役立ちます。

${\large \lfloor \frac{n}{p^l} \rfloor \\ \large = \lfloor \frac{a_0 p^0 + a_1 p^1 + a_2 p^2 + \cdots + a_mp^m}{p^l} \rfloor \\ \large = \lfloor \frac{a_0 p^0 + a_1 p^1 + a_2 p^2 + \cdots + a_{l-1}p^{l-1}}{p^l} + \frac{a_lp^l+a_{l+1}p^{l+1}+a_{l+2}p^{l+2}+ \cdots + a_mp^m}{p^l} \rfloor }$

　ここで $0 \leq a_0 p^0 + a_1 p^1 + a_2 p^2 + \cdots + a_{l-1}p^{l-1} \lt p^l$ より $0 {\large \leq \frac{a_0 p^0 + a_1 p^1 + a_2 p^2 + \cdots + a_{l-1}p^{l-1}}{p^l}} \lt 1$ であり、また、 ${\large \frac{a_lp^l+a_{l+1}p^{l+1}+a_{l+2}p^{l+2}+ \cdots + a_mp^m}{p^l}} = a_lp^0+a_{l+1}p^1+a_{l+2}p^2+ \cdots +a_mp^{m-l}$ よりこれは整数であるから、

${\large \lfloor \frac{n}{p^l} \rfloor \\ \large = \lfloor \frac{a_0 p^0 + a_1 p^1 + a_2 p^2 + \cdots + a_{l-1}p^{l-1}}{p^l} + \frac{a_lp^l+a_{l+1}p^{l+1}+a_{l+2}p^{l+2}+ \cdots + a_mp^m}{p^l} \rfloor \\ = a_lp^0+a_{l+1}p^1+a_{l+2}p^2+ \cdots +a_mp^{m-l}}$

　したがって、

$v_p(n!) \\ ={\displaystyle \sum_{l=1}^m \lfloor \frac{n}{p^l} \rfloor } \\ = {\displaystyle \sum_{l=1}^m a_lp^0+a_{l+1}p^1+a_{l+2}p^2+ \cdots +a_mp^{m-l}} \\ = (a_1p^0+a_2p^1+a_3p^2+ \cdots a_mp^{m-1}) \\ \hspace{7pt} + (a_2p^0+a_3p^1+ a_4p^2+ \cdots a_mp^{m-2}) \\ \hspace{7pt} + (a_3p^0+a_4p^1+ a_5p^2+ \cdots a_mp^{m-3}) \\ \hspace{7pt} + \cdots + a_mp^0 \\ = a_1p^0+a_2(p^0+p^1)+a_3(p^0+p^1+p^2) \\ \hspace{7pt} + \cdots + a_m(p^0+p^1+p^2+ \cdots + p^{m-1}) \\ = a_1 \frac{p^1-1}{p-1}+a_2 \frac{p^2-1}{p-1} +a_3 \frac{p^3-1}{p-1} + \cdots + a_m \frac{p^m-1}{p-1} \\ = {\large \frac{a_1(p^1-1)+a_2(p^2-1)+a_3(p^3-1)+ \cdots +a_m(p^m-1)}{p-1}} \\ = {\large \frac{(a_0p^0+a_1p^1+a_2p^2+ \cdots +a_mp^m)-(a_0+a_1+a_2+ \cdots +a_m)}{p-1}} \hspace{7pt} \because a_0p^0=a_0$

　 $n=a_0p^0+a_1p^1+a_2p^2+ \cdots +a_mp^m$ であるから、 $n$ を $p$ 進法表記したときの各位の数の和を $s_p(n)$ とおくと、

$v_p(n!)= {\large \frac{n-s_p(n)}{p-1}}$

　これをルジャンドルの定理といいます。さらに、これを使うことで $_m C_n$ を $p$ で割った余りを考えることができます。 $_m C_n = \frac{m!}{(m-n)!n!}$ より、

$v_p( _m C_n) \\ = v_p(m!) - v_p( (m-n) !) - v_p(n!) \\ = {\large \frac{(m-s_p(m))-\{ (m-n)-s_p(m-n)\} - (n-s_p(n))}{p-1}} \\ = {\large \frac{s_p(m-n)+s_p(n)-s_p(m)}{p-1}}$