概要
pを素数としたとき、
n!がpで割り切れる個数は
$$v_p(n!)=\dfrac{n-S_p(n)}{p-1}$$
である。ここで、$S_p(n)$とは、$n$を$p$進数表記したときの各桁の総和である。
証明
知らない場合は高校数学の美しい物語を見よう
つまり、
$$v_p(n!)=\sum_{k=1}^{\infty}\lfloor\dfrac{n}{p^k}\rfloor$$
任意の整数$n$は、整数$m $と0以上$p$未満の整数$a$を用いて
$$n=mp+a$$
と書くことができる。
このとき、
$$v_p(n!)=\sum_{k=1}^{\infty}\lfloor\dfrac{mp+a}{p^k}\rfloor=m+\sum_{k=2}^{\infty}\lfloor \dfrac{m}{p^{k - 1}}\rfloor=m+v_p(m!)$$
また、$n$を$p$進数表記すると$m $を$p$進数表記したものの末尾に$a$をつけたものとみなせるので
$$S_p(n)=S_p(m)+a$$
となる。
よって、
$$v_p(n!)-\dfrac{n-S_p(n)}{p-1}=m+v_p(m!)-\dfrac{mp+a-S_p(m)-a}{p-1}$$
$$=m+v_p(m!)-\dfrac{m(p-1)+m-S_p(m)}{p-1}$$
$$=m+v_p(m!)-m-\dfrac{m-S_p(m)}{p-1}$$
$$=v_p(m!)-\dfrac{m-S_p(m)}{p-1}$$
また、$m\lt p$のときは$v_p(m!)=0,S_p(m)=m $より等式は成り立つ。
よって帰納法でOK
おまけ
$$v_p(n!)=\dfrac{n-S_p(n)}{p-1}\leq \dfrac{n}{p-1}$$
という評価はありがち
まあこんなことをしなくても、
$$v_p(n!)=\sum_{k=1}^{\infty}\lfloor\dfrac{n}{p^k}\rfloor\leq \sum_{k=1}^{\infty}\dfrac{n}{p^k}=\dfrac{n}{p-1}$$
みたいなこともできる。
上で示した式はラグランジュの定理と比較すると誤差がどのくらいなのかが見えやすいという利点がある。
OMCにこの性質を使って解ける問題があったらしい
→
ところで、$v_p(n!)\leq \dfrac{n}{p-1}$という不等式は色々使えて、
$$\log{n!}=\sum_{p\leq n}v_p(n!)\log{p}\leq n\sum_{p\leq n}\dfrac{\log{p}}{p-1}$$
みたいなことができる。あとはいろいろやればなんかできるらしいです。しらんけど
