ルジャンドルの公式

テンプレート:No footnotes 数学の初等整数論におけるルジャンドルの公式（ルジャンドルのこうしき、テンプレート:Lang-en-short）とは、自然数 テンプレート:Mvar の階乗 テンプレート:Math を素数 テンプレート:Mvar で（整数の範囲で）割り切る最大回数を与える式である。テンプレート:Math を素因数分解したときの テンプレート:Mvar の冪乗の指数とも言い換えられる。アドリアン＝マリ・ルジャンドルに因んで名付けられた。ルジャンドルの定理、テンプレート:Ill2に因んでド・ポリニャックの公式とも呼ばれる。

概要

任意の非負整数 テンプレート:Mvar と任意の素数 テンプレート:Mvar に対して、 テンプレート:Mvar を割り切る最大 テンプレート:Mvar-冪の指数（すなわち、テンプレート:Mvar の [[p進付値|テンプレート:Mvar-進付値]]）を テンプレート:Math2 で表す。このとき自然数 テンプレート:Mvar に対して

${\nu }_p(n!)=\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^i}\rfloor$

が成り立つ。ここで $\lfloor x\rfloor$ は床関数である。右辺の総和は見かけ上無限和となっているが実際には、テンプレート:Math2 ならば $\lfloor \frac{n}{p^i}\rfloor =0$ となるため、テンプレート:Mvar は $\lfloor {\log }_{p}n\rfloor$ まで取ればよい。

例

テンプレート:Math2 のとき、$6!=720=2^4\cdot 3^2\cdot 5^1$ である。それぞれの指数は ${\nu }_2(6!)=4,{\nu }_3(6!)=2,{\nu }_5(6!)=1$ である。これらは以下のようにルジャンドルの公式によって計算できる。

$\begin{array}{cc}{\nu }_2(6!)& =\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{6}{2^i}\rfloor =\lfloor \frac{6}{2}\rfloor +\lfloor \frac{6}{4}\rfloor =3+1\\ {\nu }_3(6!)& =\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{6}{3^i}\rfloor =\lfloor \frac{6}{3}\rfloor =2\\ {\nu }_5(6!)& =\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{6}{5^i}\rfloor =\lfloor \frac{6}{5}\rfloor =1\end{array}$

証明

テンプレート:Math2 であるから、テンプレート:Mvar 以下の各自然数の素因数 テンプレート:Mvar の指数の総和が求める値である。まず、テンプレート:Mvar 以下の テンプレート:Mvar の正の倍数は $\lfloor \frac{n}{p}\rfloor$ 個だけある。加えて、テンプレート:Math の倍数があるごとに テンプレート:Math に素因数 テンプレート:Mvar をさらに1個見い出すことができる。テンプレート:Math 以降も同様である。故に ${\nu }_p(n!)$ はこれらの総和に等しい。

他の形式

テンプレート:Mvar を底とする テンプレート:Mvar-進展開の観点からルジャンドルの公式を定式化し直すこともできる。$s_p(n)$ を テンプレート:Mvar の テンプレート:Mvar進表記における各位の和とすると以下の式が成り立つ。

${\nu }_p(n!)=\frac{n-s_p(n)}{p-1}.$

例えば、テンプレート:Math2 を二進法で表記すると テンプレート:Math2 であり、$s_2(6)=1+1+0=2$である。したがって

${\nu }_2(6!)=\frac{6-2}{2-1}=4$

同様に、テンプレート:Math2 を三進法表示は テンプレート:Math2 であり、$s_3(6)=2+0=2$である。したがって

${\nu }_3(6!)=\frac{6-2}{3-1}=2$

である。

証明

テンプレート:Mvar は テンプレート:Mvar進法で $n=n_{\ell }{p}^{\ell }+\cdots +n_{1}p+n_0$ と書ける。したがって、$\lfloor \frac{n}{p^i}\rfloor =n_{\ell }{p}^{\ell -i}+\cdots +n_{i+1}p+n_i$ であり、

$\begin{array}{cc}{\nu }_p(n!)& =\sum _{i=1}^{\ell }\lfloor \frac{n}{p^i}\rfloor \\ & =\sum _{i=1}^{\ell }(n_{\ell }{p}^{\ell -i}+\cdots +n_{i+1}p+n_i)\\ & =\sum _{i=1}^{\ell }\sum _{j=i}^{\ell }{n}_j{p}^{j-i}\\ & =\sum _{j=1}^{\ell }\sum _{i=1}^j{n}_j{p}^{j-i}\\ & =\sum _{j=1}^{\ell }{n}_j\cdot \frac{p^j-1}{p-1}\\ & =\sum _{j=0}^{\ell }{n}_j\cdot \frac{p^j-1}{p-1}\\ & =\frac{1}{p-1}\sum _{j=0}^{\ell }(n_j{p}^j-n_j)\\ & =\frac{1}{p-1}(n-s_p(n))\end{array}$

応用

ルジャンドルの公式を用いてテンプレート:仮リンクを証明することができる。特別な場合の一つとして、テンプレート:Mvar を正の整数とすると、$(\genfrac{}{}{0ex}{}{2n}{n})$ が テンプレート:Math で割り切れるための必要十分条件は、テンプレート:Mvar が [[2の冪|テンプレート:Math の冪]]でないことである。

また、ルジャンドルの公式からは テンプレート:Ill2の収束半径は $p^{-\frac{1}{p-1}}$ であることが導ける。

参考文献

• テンプレート:Citation
• テンプレート:Citation
  • テンプレート:Cite book
• テンプレート:Citation

外部リンク

• テンプレート:高校数学の美しい物語
• テンプレート:MathWorld
• テンプレート:PlanetMath
• テンプレート:ProofWiki