n!とmCnをpで割り切れる回数について。
高校数学の教科書レベルの問題に次のようなものがあります。
「100!は3で何回割り切れるか。」
これは、
100÷3=33余り1
33÷3=11余り0
11÷3=3余り2
3÷3=1余り0
1÷3=0余り1
といった計算から、1から100までの整数に3,3²,3³,3⁴の倍数がそれぞ33,11,3,1個ずつ含まれていることが分かり、次に33+11+3+1=48とそれらの和をとることで、10!は3で48回割り切れることが分かる、というのが一般的な解法であると思います。
これは次のように一般化することができます。
「n!がpで割り切れる回数は、Σ_{k=1~∞}[n/p^k]である。」
これを「ルジャンドルの定理」といいます。
次の画像では、これを実用的な形に変形していきます。ただ、（実は数カ月前に作ったものだからと言ったら言い訳になりますが）pの条件に素数であることが含まれていません。
pが素数でなければならないのかについて、いま考えた限りでは分からなかったので、もしダメであれば脳内でpの条件を補足して読んで下さい（このブログは結構こういうガバガバなところが多いです）。
真偽を知っている人がいれば教えて頂ければ助かります。自分でも後で考えてみます。間違えているとしたら、多分すごく初歩的な理由なんだろうな…
【補足(7/22)】ダメでした。例えば、6,6²,6³,...の倍数の個数を調べても、それらに含まれていない2の倍数や3の倍数が存在するので、6で割り切れる回数とズレてきます。
「nをp進表記したときの各桁の和」が登場するのは、これを証明した時に初めて見たので感動しました。簡単な問題でも、掘り下げればこういう発見があるということに気づかされました。
ちなみに実際にこれで計算しようとしたら分かると思いますが、結局は似たような計算をすることになりますので、計算が早くなるかといえば余り変わらないと思います。
次に、これを利用して次の「クンマーの定理」と呼ばれるものを証明します。これはすぐ終わります。
この定理は非常にマイナーなようで、Wikipediaの記事も英語版しかありません（7/22現在）。僕は「高校数学の美しい物語」で証明を読ませていただきました。
証明の著作権について、特に表現の点が気になったので少し雑な感じになってしまいました。他のサイトの証明も見て書きたかったのですが、クンマーは他のサイトばかりヒットして、見つけられませんでした。
それはさておき、これは「p進法でm-nとnを足し算した時の繰り上がりの回数」という、さっき以上に意外な結果がでました。
使える場面の少なさから「ルジャンドルの定理」「クンマーの定理」は、このブログで（二人の数学者には失礼ですが）第三、第四の「使わない公式」に認定しようと思うのですが、個人的には非常に好きです。
最後に、nが非常に大きいときn!はpでだいたい何回くらい割り切れるのか考えていきます。（これも一枚目同様、数カ月前に作ったものです）
したがって、nが十分に大きいときv_p(n)≒n/(p-1)が成り立つことが分かります。
これは絶対に使う場面はないですね。これこそ使わない公式に入れるべき。ちなみに、最終的には使わない100の公式リストを作ることが僕の目標です。
多分、よく見る高校数学の一般化が大部分を占めますが、ときどき既存の定理・公式についても含みます。ただ、そのときは闇雲に「これ使わねーだろ！」って思ったものを入れるのではなく、同時に「でも面白い！」って思ったものに限ることにします。それと、「使わない」の基準は飽くまで高校数学の範囲と僕の偏見です（）
謎の抱負もこれくらいにしましょう。今回、自分に課された宿題はpの条件についてです。マジで基礎的な内容じゃないかと不安ですが、知っている方いたら遠慮なく教えてください。頭硬いので時間を溶かしてしまいそうで怖いｗ
ではではー。
【補足２(7/22)】最後の極限を使えば、pが素数でないといけないことがより明確に示せました。しっかりと理解して数学をしている人はそもそもこんなミスをしないはずなので、最後に求めた極限の応用くらいに思って読んで下さい。
v'_p(n)はpが素数でなくてもv_p(n)の性質が成り立つと仮定した関数とします。このとき、間違えた数え方をしたときに数え漏らす回数の割合を求めます。
pが素数でない、すなわちd(p)≠pのとき、この極限は正であるから、数え漏らしがあることになります。たとえばp=6とすると、この極限は3/5に収束するので、間違えた数え方をするとnが十分に大きいとき約3/5を数え漏らすことになります。
