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.
Statement For any prime number p and any positive integer n, let ν p ( n ) {\displaystyle \nu _{p}(n)} be the exponent of the largest power of p that divides n (that is, the p-adic valuation of n). Then
ν p ( n ! ) = ∑ i = 1 ∞ ⌊ n p i ⌋ , {\displaystyle \nu _{p}(n!)=\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor ,}
where ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } 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 p i > n {\displaystyle p^{i}>n} , one has ⌊ n p i ⌋ = 0 {\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =0} . This reduces the infinite sum above to
ν p ( n ! ) = ∑ i = 1 L ⌊ n p i ⌋ , {\displaystyle \nu _{p}(n!)=\sum _{i=1}^{L}\left\lfloor {\frac {n}{p^{i}}}\right\rfloor \,,}
where L = ⌊ log p n ⌋ {\displaystyle L=\lfloor \log _{p}n\rfloor } .
Example For n = 6, one has 6 ! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋅ 6 = 2 4 ⋅ 3 2 ⋅ 5 1 {\displaystyle 6!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6=2^{4}\cdot 3^{2}\cdot 5^{1}} . The exponents ν 2 ( 6 ! ) = 4 {\displaystyle \nu _{2}(6!)=4} , ν 3 ( 6 ! ) = 2 {\displaystyle \nu _{3}(6!)=2} , and ν 5 ( 6 ! ) = 1 {\displaystyle \nu _{5}(6!)=1} can be computed by Legendre's formula as follows:
… excerpt ends here. Continue reading the full article.
