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 after Adrien-Marie Legendre.
It is also sometimes known as de Polignac's formula, after Alphonse de Polignac.
For any prime number p and any positive integer n, let
ν
be the exponent of the largest power of p that divides n (that is, the p-adic valuation of n).
is the floor function.
While the sum on the right side is an infinite sum, for any particular values of n and p it has only finitely many nonzero terms: for every i large enough that
This reduces the infinite sum above to where
ν
ν
ν
can be computed by Legendre's formula as follows: Since
is the product of the integers 1 through n, we obtain at least one factor of p in
contributes an additional factor of p, each multiple of
contributes yet another factor of p, etc.
Adding up the number of these factors gives the infinite sum for
ν
One may also reformulate Legendre's formula in terms of the base-p expansion of n. Let
denote the sum of the digits in the base-p expansion of n; then For example, writing n = 6 in binary as 610 = 1102, we have that
and so Similarly, writing 6 in ternary as 610 = 203, we have that
and so Write
ℓ
ℓ
in base p. Then
ℓ
ℓ − i
, and therefore Legendre's formula can be used to prove Kummer's theorem.
As one special case, it can be used to prove that if n is a positive integer then 4 divides
It follows from Legendre's formula that the p-adic exponential function has radius of convergence