出典: フリー百科事典『ウィキペディア（Wikipedia）』
数学 の初等整数論 におけるルジャンドルの公式 （ルジャンドルのこうしき、英 : 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 = 66(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 = 66(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 
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afbc95ffb72532a142aca08dfc755308fa58c58e)
