ルジャンドルの公式

初等整数論におけるルジャンドルの公式（ルジャンドルのこうしき、英: Legendre's formula）は、素数 p に対して階乗 n! を割り切る p の最大の冪乗の指数を与える式である。アドリアン＝マリ・ルジャンドルにちなんで名付けられた。ルジャンドルの定理、アルフォンス・ド・ポリニャック（英語版）にちなんでド・ポリニャックの公式とも呼ばれる。 任意の素数 p と任意の非負整数 n に対して、νp(n) は n を割り切る最大 p-冪の指数（すなわち、n の p-進付値）を表す記号とする。このとき、 ν p ( n ! ) = ∑ i = 1 ∞ ⌊ n p i ⌋ {\displaystyle \nu _{p}(n!)=\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor } である。但しここで、 ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } は床関数である。式の右辺に見かけ上の無限和が現れているけれども、n および p が固定されれば現れる非零項は有限個しかない: 実際、i を十分大きく pi > n なるようにとれば ⌊ n p i ⌋ = 0 {\textstyle \lfloor {\frac {n}{p^{i}}}\rfloor =0} が成り立つ。 n=6 のとき、 6 ! = 720 = 2 4 ⋅ 3 2 ⋅ 5 1 {\displaystyle 6!=720=2^{4}\cdot 3^{2}\cdot 5^{1}} である。それぞれの指数は ν 2 ( 6 ! ) = 4 , ν 3 ( 6 ! ) = 2 , ν 5 ( 6 ! ) = 1 {\displaystyle \nu _{2}(6!)=4,\nu _{3}(6!)=2,\nu _{5}(6!)=1} である。これらは以下のようにルジャンドルの公式によって計算できる。 ν 2 ( 6 ! ) = ∑ i = 1 ∞ ⌊ 6 2 i ⌋ = ⌊ 6 2 ⌋ + ⌊ 6 4 ⌋ = 3 + 1 ν 3 ( 6 ! ) = ∑ i = 1 ∞ ⌊ 6 3 i ⌋ = ⌊ 6 3 ⌋ = 2 ν 5 ( 6 ! ) = ∑ i = 1 ∞ ⌊ 6 5 i ⌋ = ⌊ 6 5 ⌋ = 1 {\displaystyle {\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までの積である。まず、1からnまでの範囲にあるpの倍数1つごとに、n!の素因数pを少なくとも1つ見いだすことができる。pの倍数はnまでに ⌊ n p ⌋ {\displaystyle \textstyle \left\lfloor {\frac {n}{p}}\right\rfloor } 個存在する。また、p2の倍数があるごとにn!に素因数pをさらに1個見いだすことができる。p3以降も同様である。これらを全て加えることによって、無限和で ν p ( n ! ) {\displaystyle \nu _{p}(n!)} を表すことが可能である。 p を底とする p-進展開の観点からルジャンドルの公式を定式化し直すこともできる。 s p ( n ) {\displaystyle s_{p}(n)} をnのp進表記における各位の和とすると以下の式が成り立つ。 ν p ( n ! ) = n − s p ( n ) p − 1 . {\displaystyle \nu _{p}(n!)={\frac {n-s_{p}(n)}{p-1}}.} 例えば、n =6を二進法で表記すると 610=1102 であり、 s 2 ( 6 ) = 1 + 1 + 0 = 2 {\displaystyle s_{2}(6)=1+1+0=2} である。したがって ν 2 ( 6 ! ) = 6 − 2 2 − 1 = 4 {\displaystyle \nu _{2}(6!)={\frac {6-2}{2-1}}=4} 同様に、n =6を三進法で表記すると 610=203 であり、 s 3 ( 6 ) = 2 + 0 = 2 {\displaystyle s_{3}(6)=2+0=2} である。したがって ν 3 ( 6 ! ) = 6 − 2 3 − 1 = 2 {\displaystyle \nu _{3}(6!)={\frac {6-2}{3-1}}=2} である。 nはp進法で n = n ℓ p ℓ + ⋯ + n 1 p + n 0 {\displaystyle n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}} と書ける。したがって、 ⌊ n p i ⌋ = n ℓ p ℓ − i + ⋯ + n i + 1 p + n i {\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}} であり、 ν p ( n ! ) = ∑ i = 1 ℓ ⌊ n p i ⌋ = ∑ i = 1 ℓ ( n ℓ p ℓ − i + ⋯ + n i + 1 p + n i ) = ∑ i = 1 ℓ ∑ j = i ℓ n j p j − i = ∑ j = 1 ℓ ∑ i = 1 j n j p j − i = ∑ j = 1 ℓ n j ⋅ p j − 1 p − 1 = ∑ j = 0 ℓ n j ⋅ p j − 1 p − 1 = 1 p − 1 ∑ j = 0 ℓ ( n j p j − n j ) = 1 p − 1 ( n − s p ( n ) ) {\displaystyle {\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 を正の整数とすると、 ( 2 n n ) {\textstyle {\binom {2n}{n}}} が 4 で割り切れるための必要十分条件は、n が 2 の冪でないことである。 また、ルジャンドルの公式からは p-進指数関数（英語版）が収束半径 p − 1 / ( p − 1 ) {\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  『ルジャンドルの定理（階乗が持つ素因数のべき数）』 - 高校数学の美しい物語 Weisstein, Eric W. "Factorial". mathworld.wolfram.com (英語). de Polignac’s formula - PlanetMath.（英語） De Polignac's Formula at ProofWiki