数学 の初等整数論 におけるルジャンドルの公式 (ルジャンドルのこうしき、英 : Legendre's formula )とは、自然数 n の階乗 n ! を素数 p で(整数の範囲で)割り切る最大回数を与える式である。n ! を素因数分解 したときの p の冪乗 の指数とも言い換えられる。アドリアン=マリ・ルジャンドル に因んで名付けられた。ルジャンドルの定理 、アルフォンス・ド・ポリニャック (英語版 ) に因んでド・ポリニャックの公式 とも呼ばれる。
任意の非負整数 N と任意の素数 p に対して、 N を割り切る最大 p -冪の指数(すなわち、n の p -進付値 )を νp (N ) で表す。このとき自然数 n に対して
ν p ( n ! ) = ∑ i = 1 ∞ ⌊ n p i ⌋ {\displaystyle \nu _{p}(n!)=\textstyle \sum \limits _{i=1}^{\infty }\left\lfloor {\dfrac {n}{p^{i}}}\right\rfloor } が成り立つ。ここで ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } は床関数 である。右辺の総和は見かけ上無限和となっているが実際には、pi > n ならば ⌊ n p i ⌋ = 0 {\displaystyle \left\lfloor {\tfrac {n}{p^{i}}}\right\rfloor =0} となるため、i は ⌊ log p n ⌋ {\displaystyle \lfloor \log _{p}n\rfloor } まで取ればよい。
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!)&=\textstyle \sum \limits _{i=1}^{\infty }\left\lfloor {\dfrac {6}{2^{i}}}\right\rfloor =\left\lfloor {\dfrac {6}{2}}\right\rfloor +\left\lfloor {\dfrac {6}{4}}\right\rfloor =3+1\\[3pt]\nu _{3}(6!)&=\textstyle \sum \limits _{i=1}^{\infty }\left\lfloor {\dfrac {6}{3^{i}}}\right\rfloor =\left\lfloor {\dfrac {6}{3}}\right\rfloor =2\\[3pt]\nu _{5}(6!)&=\textstyle \sum \limits _{i=1}^{\infty }\left\lfloor {\dfrac {6}{5^{i}}}\right\rfloor =\left\lfloor {\dfrac {6}{5}}\right\rfloor =1\end{aligned}}} n ! = 1 × … × n であるから、n 以下の各自然数の素因数 p の指数の総和が求める値である。まず、n 以下の p の正の倍数は ⌊ n p ⌋ {\displaystyle \left\lfloor {\tfrac {n}{p}}\right\rfloor } 個だけある。加えて、p 2 の倍数があるごとに n ! に素因数 p をさらに1個見い出すことができる。p 3 以降も同様である。故に ν 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 を二進法で表記すると 6(10) = 110(2) であり、 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 を三進法表示は 6(10) = 20(3) であり、 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 \left\lfloor {\tfrac {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!)&=\textstyle \sum \limits _{i=1}^{\ell }\left\lfloor {\dfrac {n}{p^{i}}}\right\rfloor \\&=\textstyle \sum \limits _{i=1}^{\ell }(n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i})\\&=\textstyle \sum \limits _{i=1}^{\ell }\sum \limits _{j=i}^{\ell }n_{j}p^{j-i}\\&=\textstyle \sum \limits _{j=1}^{\ell }\sum \limits _{i=1}^{j}n_{j}p^{j-i}\\&=\textstyle \sum \limits _{j=1}^{\ell }n_{j}\cdot {\dfrac {p^{j}-1}{p-1}}\\&=\textstyle \sum \limits _{j=0}^{\ell }n_{j}\cdot {\dfrac {p^{j}-1}{p-1}}\\&={\frac {1}{p-1}}\textstyle \sum \limits _{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 ) {\displaystyle {\tbinom {2n}{n}}} が 4 で割り切れるための必要十分条件 は、n が 2 の冪 でないことである。
また、ルジャンドルの公式からは p -進指数関数(英語版 ) の収束半径 は p − 1 p − 1 {\displaystyle p^{-{\tfrac {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 , Paris: Firmin Didot Frères Moll, Victor H. (2012), Numbers and Functions , American Mathematical Society , p. 77, ISBN 978-0-8218-8795-0 , MR 2963308 外部リンク [ 編集 ]