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 ) .
