Trong toán học, Công thức Legendre là biểu thức tính số mũ của lũy thừa lớn nhất của số nguyên tố p mà là ước của n !. Công thức được đặt tên theo nhà toán học Adrien-Marie Legendre . Đôi khi nó cũng được gọi là công thức de Polignac , theo tên của Alphonse de Polignac .
Cho số nguyên tố p và bất kỳ số tự nhiên n , gọi
ν
p
(
n
)
{\displaystyle \nu _{p}(n)}
là số mũ của lũy thừa lớn nhất p mà là ước của n (tức là định giá p -adic của n ). Khi đó
ν
p
(
n
!
)
=
∑
i
=
1
∞
⌊
n
p
i
⌋
,
{\displaystyle \nu _{p}(n!)=\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor ,}
trong đó
⌊
x
⌋
{\displaystyle \lfloor x\rfloor }
là hàm lấy phần nguyên . Mặc dù tổng ở vế phải có vô hạn số phần tử, cho bất kỳ giá trị của n và p , nó vẫn chỉ có hữu hạn số phần tử khác không, lý do như sau: lấy các giá trị i đủ lớn sao cho
p
i
>
n
{\displaystyle p^{i}>n}
, ta có
⌊
n
p
i
⌋
=
0
{\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =0}
. Nhờ đó, rút gọn công thức trên thành
ν
p
(
n
!
)
=
∑
i
=
1
L
⌊
n
p
i
⌋
,
{\displaystyle \nu _{p}(n!)=\sum _{i=1}^{L}\left\lfloor {\frac {n}{p^{i}}}\right\rfloor \,,}
trong đó
L
=
⌊
log
p
n
⌋
{\displaystyle L=\lfloor \log _{p}n\rfloor }
.
Xét n = 6, ta có
6
!
=
720
=
2
4
⋅
3
2
⋅
5
1
{\displaystyle 6!=720=2^{4}\cdot 3^{2}\cdot 5^{1}}
. Các số mũ
ν
2
(
6
!
)
=
4
,
ν
3
(
6
!
)
=
2
{\displaystyle \nu _{2}(6!)=4,\nu _{3}(6!)=2}
và
ν
5
(
6
!
)
=
1
{\displaystyle \nu _{5}(6!)=1}
có thể tính bằng công thức Legendre như sau:
ν
2
(
6
!
)
=
∑
i
=
1
∞
⌊
6
2
i
⌋
=
⌊
6
2
⌋
+
⌊
6
4
⌋
=
3
+
1
=
4
,
ν
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=4,\\[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}}}
Bởi
n
!
{\displaystyle n!}
là tích của các số nguyên dương từ 1 đến n , ta thu được ít nhất một p trong
n
!
{\displaystyle n!}
cho mỗi bội của p trpng
{
1
,
2
,
…
,
n
}
{\displaystyle \{1,2,\dots ,n\}}
, tổng cộng có
⌊
n
p
⌋
{\displaystyle \textstyle \left\lfloor {\frac {n}{p}}\right\rfloor }
. Mỗi bội của
p
2
{\displaystyle p^{2}}
cho thêm một nhân tử p , và tương tự như vậy, mỗi bội của
p
3
{\displaystyle p^{3}}
cho thêm một nhân tử p , tiếp diễn như vậy cho các lũy thừa sau. Cộng tất cả số này sẽ thu về được công thức tổng vô hạn cho
ν
p
(
n
!
)
{\displaystyle \nu _{p}(n!)}
.
Ta cũng có thể viết lại công thức Legendre thành khai triển cơ số p của n . Gọi
s
p
(
n
)
{\displaystyle s_{p}(n)}
là tổng các chữ số trong khai triển cơ số p của n thì
ν
p
(
n
!
)
=
n
−
s
p
(
n
)
p
−
1
.
{\displaystyle \nu _{p}(n!)={\frac {n-s_{p}(n)}{p-1}}.}
Ví dụ chẳng hạn, n = 6 trong hệ nhị phân được viết là 610 = 1102 , ta có
s
2
(
6
)
=
1
+
1
+
0
=
2
{\displaystyle s_{2}(6)=1+1+0=2}
nên
ν
2
(
6
!
)
=
6
−
2
2
−
1
=
4.
{\displaystyle \nu _{2}(6!)={\frac {6-2}{2-1}}=4.}
Tương tự, n = 6 trong hệ tam phân được viết là 610 = 203 , ta có
s
3
(
6
)
=
2
+
0
=
2
{\displaystyle s_{3}(6)=2+0=2}
nên
ν
3
(
6
!
)
=
6
−
2
3
−
1
=
2.
{\displaystyle \nu _{3}(6!)={\frac {6-2}{3-1}}=2.}
Viết
n
=
n
ℓ
p
ℓ
+
⋯
+
n
1
p
+
n
0
{\displaystyle n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}}
trong hệ cơ số p . Vì
⌊
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}}
, và do vậy
ν
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}}}
Công thức Legendre được dùng để chứng minh định lý Kummer . Dưới trường hợp đặc biệt, nó có thể dùng để chứng minh rằng nếu n là số nguyên dương thì
(
2
n
n
)
{\displaystyle {\binom {2n}{n}}}
chia hết cho 4 khi và chỉ khi n không phải lũy thừa của 2.
Suy ra được từ công thức Legendre rằng hàm mũ p -adic có bán kính hội tụ bằng với
p
−
1
/
(
p
−
1
)
{\displaystyle p^{-1/(p-1)}}
.
Legendre, A. M. (1830), Théorie des Nombres , Paris: Firmin Didot Frères
Moll, Victor H. (2012), Numbers and Functions , American Mathematical Society , ISBN 978-0821887950 , MR 2963308 , page 77
Leonard Eugene Dickson , History of the Theory of Numbers , Volume 1, Carnegie Institution of Washington, 1919, page 263.