ルジャンドルの公式

初等整数論におけるルジャンドルの公式（ルジャンドルのこうしき、英: Legendre's formula）は、任意の素数 $p$ に対して階乗 $n!$ を割り切る $p$ の最大冪の冪指数を与える式である。アドリアン＝マリ・ルジャンドルにちなんで名付けられた。ルジャンドルの定理、アルフォンス・ド・ポリニャック（英語版）に因んでドポリニャクの公式とも呼ばれる。

概要

任意の素数 $p$ と任意の非負整数 $n$ に対して、 $ν p (n)$ は $n$ を割り切る最大 $p$ -冪の冪指数（すなわち、 $n$ の $p$ -進付値）とすれば、

\nu _{p}(n!)=\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor

である。但しここで、 $\lfloor x\rfloor$ は床関数である。式の右辺に見かけ上の無限和が現れているけれども、 $n$ および $p$ が固定されれば現れる非零項は有限個しかない: 実際、 $i$ を十分大きく $p i > n$ なるようにとれば ${\textstyle \lfloor {\frac {n}{p^{i}}}\rfloor =0}$ が成り立つ。

例

n =6のとき、 $6!=720=2^{4}\cdot 3^{2}\cdot 5^{1}$ である。したがってそれぞれの次数より $\nu _{2}(6!)=4,\nu _{3}(6!)=2,\nu _{5}(6!)=1$ である。これらは以下のようにルジャンドル式で計算できる。

{\begin{aligned}\nu _{2}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{2^{i}}}\right\rfloor =\left\lfloor {\frac {6}{2}}\right\rfloor +\left\lfloor {\frac {6}{4}}\right\rfloor =3+1\\[3pt]\nu _{3}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{3^{i}}}\right\rfloor =\left\lfloor {\frac {6}{3}}\right\rfloor =2\\[3pt]\nu _{5}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{5^{i}}}\right\rfloor =\left\lfloor {\frac {6}{5}}\right\rfloor =1\end{aligned}}

証明

n!は1からnまでの積である。n!を割り切るpの次数を調べるために、まずn!の約数であるpの倍数の個数を数える。pの倍数はnまでに $\textstyle \left\lfloor {\frac {n}{p}}\right\rfloor$ 個存在する。また、p²の倍数はn!にさらに1個の約数としてpを持たせ、p³以降も同様である。これを全て加えることによって、無限和で $\nu _{p}(n!)$ を表すことが可能である。

他の形式

$p$ を底とする $p$ -進展開の観点からルジャンドルの公式を定式化し直すこともできる。 $s_{p}(n)$ をnのp進表記での各桁の合計とすると以下の数式が成り立つ。

\nu _{p}(n!)={\frac {n-s_{p}(n)}{p-1}}.

例えば、n =6を二進法で表記すると6₁₀ =110₂であり、 $s_{2}(6)=1+1+0=2$ である。したがって

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

同様に、n=6を三進法で表記すると6₁₀ =20₃であり、 $s_{3}(6)=2+0=2$ である。したがって

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

である。

証明

nはp進法で $n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}$ と書ける。したがって、 $\textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}$ であり、

{\begin{aligned}\nu _{p}(n!)&=\sum _{i=1}^{\ell }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor \\&=\sum _{i=1}^{\ell }\left(n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}\right)\\&=\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 }\left(n_{j}p^{j}-n_{j}\right)\\&={\frac {1}{p-1}}\left(n-s_{p}(n)\right)\end{aligned}}

応用

ルジャンドルの公式はクンマーの定理（英語版）の証明に使われる。特別な場合の一つとして、 $n$ が正の整数である場合には、 ${\textstyle {\binom {2n}{n}}}$ が $4$ で割り切れるための必要十分条件は、 $n$ が $2$ の冪でないことである。

これはルジャンドルの公式により $p$ -進指数関数（英語版）が収束半径 ${\textstyle p^{-1/(p-1)}}$ を持つことから導ける。

参考文献

Dickson, Leonard Eugene (2005) [1830], History of the Theory of Numbers, Volume 1: Divisibility and Primality, Dover Publications, p. 263, ISBN 978-0-486-44232-7
Legendre, A. M. (1830), Théorie des Nombres, Paris: Firmin Didot Frères
- AｰM. ルジャンドル著、高瀬正仁訳『数の理論』海鳴社、2007年12月。ISBN 978-4-87525-245-0。
Moll, Victor H. (2012), Numbers and Functions, American Mathematical Society, p. 77, ISBN 978-0-8218-8795-0, MR2963308

外部リンク

『{{{2}}}』 - 高校数学の美しい物語
Weisstein, Eric W. "Factorial". mathworld.wolfram.com (英語).
de Polignac’s formula - PlanetMath.（英語）
De Polignac's Formula at ProofWiki