【数論】ルジャンドルの公式とは？ 主張・証明・別の形式・例題まで解説
こんにちは！半沢です！
今回の記事では数論におけるルジャンドルの公式(Legendre’s formula)について解説します。
ルジャンドルの公式は高校数学の問題でも使われる一方，\(\,p\,\)進数といった大学数学の分野においても使われます。
ルジャンドルの公式の主張・証明や，なかなか知られていない別の形式，そして高校数学の例題までも取り扱っています。
ぜひ読んでいってください。
ルジャンドルの公式(Legendre’s formula)
主張
ルジャンドルの公式
\(n!\,\)を素因数分解したときの素因数\(\,p\,\)の個数を\(\,v_p(n!)\,\)で表すとすると，次の公式で求められる。
\(v_p(n!)=\displaystyle \sum_{k=1}^{\infty}\biggl\lfloor\dfrac{n}{p^{k}}\biggr\rfloor\)
※記号\(\,\lfloor x\rfloor \,\)は実数\(\,x\,\)を越えない最大の整数を表すガウス記号(床関数)のことです。
無限和が登場しているように見えますが，
\(k\,\)が十分に大きいとき\(\,\dfrac{n}{p^{k}}\lt 1\,\)，つまり\(\,\biggl\lfloor \dfrac{n}{p^k}\biggr\rfloor=0\,\)となり消えるので，
有限和と考えて良いです。
証明，ルジャンドルの公式の別の形式，高校数学での例題をそれぞれ紹介しているので，必要に応じてご覧ください。
大学数学では\(\,p\,\)進指数関数の収束域や等長性の証明に使われているので，かなり味わい深い定理になっています。
※勘の良い方は\(\,v_p(n!)\,\)という表式で「\(\,p\,\)進付値に関係がありそうだな」と思ったことでしょう。
証明
この節ではルジャンドルの公式の証明を行っていきたいと思います。
まずは具体的な\(\,n=10,p=2\,\)の場合について考えましょう。
\(10\gt 2^4=16\,\)なので，\(\,\biggl\lfloor\dfrac{10}{2^{k}}\biggr\rfloor=0\,\,(k\geq 4)\,\)です。
そこでそれら以外の\(\,\biggl\lfloor\dfrac{10}{2^1}\biggr\rfloor,\biggl\lfloor\dfrac{10}{2^2}\biggr\rfloor,\biggl\lfloor\dfrac{10}{2^3}\biggr\rfloor\,\)の意味を考えていきましょう。
すると
\(\biggl\lfloor\dfrac{10}{2^1}\biggr\rfloor\,\)は\(\,1\sim 10\,\)までの数で素因数\(\,2\,\)を\(\,1\,\)個以上持つ数の個数。
\(\biggl\lfloor\dfrac{10}{2^2}\biggr\rfloor\,\)は\(\,1\sim 10\,\)までの数で素因数\(\,2\,\)を\(\,2\,\)個以上持つ数の個数。
\(\biggl\lfloor\dfrac{10}{2^3}\biggr\rfloor\,\)は\(\,1\sim 10\,\)までの数で素因数\(\,2\,\)を\(\,3\,\)個以上持つ数の個数。
と考えられます。
したがって下の表で各行ごとに\(\,\bigcirc\,\)を数え上げることで
和\(\,\biggl\lfloor\dfrac{10}{2^1}\biggr\rfloor+\biggl\lfloor\dfrac{10}{2^2}\biggr\rfloor+\biggl\lfloor\dfrac{10}{2^3}\biggr\rfloor\,\)は下の表の\(\,\bigcirc\,\)の個数となります。
今度は表を列で考えれば\(\,1\sim 10\,\)のそれぞれの数の下にある\(\,\bigcirc\,\)の数が，その数が持つ素因数\(\,2\,\)の個数になります。
確かに\(\,4=2^2\,\)の下には\(\,\bigcirc\,\)が\(\,2\,\)つあることが分かると思います。
そのため表で各列ごとに\(\,\bigcirc\,\)を数え上げることで
\(10!\,\)を素因数分解したときの素因数\(\,2\,\)の個数\(\,v_2(10!)\,\)は表の\(\,\bigcirc\,\)の個数となります。
※ここの「\(\,v_p(n!)\,\)が\(\,\bigcirc\,\)の個数となる」ところに\(\,p\,\)が素数である仮定が使われています。
例えば\(\,p\,\)が素数でない\(\,n=3,p=6\,\)の場合を考えてみると成り立たない理由が直感的に分かると思います。
したがって
\(\,v_2(10!)=\biggl\lfloor\dfrac{10}{2^1}\biggr\rfloor+\biggl\lfloor\dfrac{10}{2^2}\biggr\rfloor+\biggl\lfloor\dfrac{10}{2^3}\biggr\rfloor=\displaystyle \sum_{k=1}^{\infty} \biggl\lfloor\dfrac{10}{2^k}\biggr\rfloor\,\)
となります。
一般の場合も全く同様の考え方によって
\(v_p(n!)=\displaystyle \sum_{k=1}^{\infty}\biggl\lfloor\dfrac{n}{p^{k}}\biggr\rfloor\)
が成り立ちます。
したがって題意は示されました。\(\quad\square\)
別の形式
ルジャンドルの公式の別の形式として，以下の形も知られています。
ルジャンドルの公式(別ver.)
自然数\(\,n\,\)を\(\,p\,\)進法で表すと\(\,n=a_0a_1\cdots a_m {}_{(p)}\,\)と書けたとする(\(\,p\,\)は素数)。
このとき各桁の数の和を\(\,s=a_0+a_1+\cdots+a_m\,\)とおくと，
\(n!\,\)を素因数分解したときの素因数\(\,p\,\)の個数\(\,v_p(n!)\,\)は次の公式で与えられる。
\(v_p(n!)=\dfrac{n-s}{p-1}\)
こちらの形式の方がより便利な印象です。実際\(\,p\,\)進指数関数の記事の中の証明でも用いています。
ここからは別ver.の証明を確認していきましょう。
まず\(\,p\,\)進法表記から\(\,n=a_0+a_1p+\cdots+a_mp^{m}\lt p^{m+1}\,\)なので，
\(k\gt m+1\,\)のとき\(\,\biggl\lfloor\dfrac{n}{p^{k}}\biggr\rfloor=0\,\)となります。
よって元の表式から
\(v_p(n!)=\displaystyle \sum_{k=1}^{\infty}\biggl\lfloor\dfrac{n}{p^{k}}\biggr\rfloor=\sum_{k=1}^{m}\biggl\lfloor\dfrac{n}{p^{k}}\biggr\rfloor\)
となります。ここでさらに各項\(\,\displaystyle \biggl\lfloor\dfrac{n}{p^{k}}\biggr\rfloor\,\,(k\leq m)\,\)について考えていきましょう。
\(\dfrac{n}{p^{k}}=\underbrace{\dfrac{a_0+a_1p+\cdots+a_{k-1}p^{k-1}}{p^k}}_{1より小さい}+a_k+\cdots+a_mp^{m-k}\)
なので，
\(\biggl\lfloor\dfrac{n}{p^{k}}\biggr\rfloor=a_k+\cdots+a_mp^{m-k}\)
となります。
これを利用すると次のように式変形できます。
したがって題意は示されました。\(\quad\square\)
例題
ここでは高校数学の範囲でルジャンドルの公式を使う例題を\(\,2\,\)つ紹介しましょう。
例題1:京大2018年度文系問5
京大の問題と言っても，ルジャンドルの公式を知っていれば瞬殺です。
\((p^n)!\,\)を素因数分解したときの素因数\(\,p\,\)の個数\(\,v_p((p^n)!)\,\)を求めれば良いだけです。
と求められるので，答えは\(\,\dfrac{p^n-1}{p-1}\,\)回となります。
実は別ver.の方がもっと楽に解けます。
\(p^{n}\,\)を\(\,p\,\)進法で表すと明らかに
\(p^n=1\underbrace{00\cdots 00}_{n個}{}_{(p)}\,\)
となるので，\(\,p\,\)進法での各桁の和\(\,s\,\)は\(\,1\,\)となります。
よってルジャンドルの公式(別ver.)からも
\(v_p(p^n!)=\dfrac{p^n-1}{p-1}\)
と求めることができます。
例題2:\(\,\sqrt[n]{n!}\,\)が自然数となるのはいつ？
こちらの問題にもルジャンドルの公式が使えます。
まず\(\,n=1\,\)のときは\(\,\sqrt[1]{1!}=1\,\)より，確かに自然数になりますね。
よって\(\,n\geq 2\,\)のときを考えましょう。
素因数分解から少なくとも\(\,n\,\)はなんらかの素数\(\,p\,\)で割り切れます。
つまり\(\,v_p(n!)\geq 1\,\)であるような素数\(\,p\,\)が存在するということですね。
さらにこの素数\(\,p\,\)について
ルジャンドルの公式において，ガウス記号の不等式\(\,\lfloor x\rfloor \leq x\,\)を用いれば
\(v_p(n!)\,\)を次のように上から評価できます。
\(v_p(n!)=\displaystyle \sum_{k=1}^{\infty}\biggl\lfloor\dfrac{n}{p^{k}}\biggr\rfloor\lt \sum_{k=1}^{\infty}\dfrac{n}{p^{k}}=\dfrac{n}{p-1}\leq n\,\)
となります。
まとめると\(\,1\leq \,v_p(n!)\lt n\,\)となります。
\(\sqrt[n]{n!}\,\)が自然数となるためには，\(\,n!\,\)の素因数\(\,p\,\)の数\(\,v_p(n!)\,\)は\(\,n\,\)で割り切れる必要があります。
しかし\(\,1\leq \,v_p(n!)\lt n\,\)となっているため，これはあり得ません。
よって\(\,n\geq 2\,\)のとき\(\,\sqrt[n]{n!}\,\)が自然数にならないことが示されました。
したがって題意は示されました。\(\quad\square\)
ちなみにルジャンドルの公式(別ver.)でも\(\,p\,\)進表示の各桁の和\(\,s\,\)は\(\,0\,\)より大きいことを利用すると
\(v_p(n!)=\dfrac{n-s}{p-1}\lt \dfrac{n}{p-1}\leq n \)
より同様の評価\(\,1\leq \,v_p(n!)\lt n\,\)が得られます。
まとめ
今回の記事ではルジャンドルの公式(Legendre’s formula)を解説いたしました。
ルジャンドルの公式の別ver.はあまり知られていないので，この記事で覚えていただけると嬉しいです。
もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。
ここまで読んでいただき，ありがとうございました。
