In mathematics, Legendre's formula gives an expression for the exponent of the largest power of a prime p that divides the factorial
n
!
. It is named for Adrien-Marie Legendre.
Let p be a prime and n be a positive integer. Let
ν
p
(
n
)
denote the p-adic valuation of n. Then
ν
p
(
n
!
)
=
∑
i
=
1
∞
⌊
n
p
i
⌋
,
where
⌊
x
⌋
is the floor function. Equivalently, if
s
p
(
n
)
denotes the sum of the standard base-p digits of n, then
ν
p
(
n
!
)
=
n
−
s
p
(
n
)
p
−
1
.
Since
n
!
is the product of the integers 1 through n, we obtain at least one factor of p in
n
!
for each multiple of p in
{
1
,
2
,
…
,
n
}
, of which there are
⌊
n
p
⌋
. Each multiple of
p
2
contributes an additional factor of p, each multiple of
p
3
contributes yet another factor of p, etc. Adding up the number of these factors gives the infinite sum for
ν
p
(
n
!
)
. The sum contains only finitely many nonzero terms, since
⌊
n
p
i
⌋
=
0
for
p
i
>
n
.
To obtain the second form, write
n
=
n
ℓ
p
ℓ
+
⋯
+
n
1
p
+
n
0
in base p. Then
⌊
n
p
i
⌋
=
n
ℓ
p
ℓ
−
i
+
⋯
+
n
i
+
1
p
+
n
i
, and therefore
ν
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
)
)
.
For
p
=
2
, we obtain
ν
2
(
n
!
)
=
n
−
s
2
(
n
)
where
s
2
(
n
)
is the number of 1s in the binary representation of n.
This can be used to prove that if
n
is a positive integer, then
4
divides
(
2
n
n
)
if and only if
n
is not a power of
2
.
Legendre's formula can be used to prove Kummer's theorem.
It follows from Legendre's formula that the p-adic exponential function has radius of convergence
p
−
1
/
(
p
−
1
)
.
