Legendre's formula explained

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

\nu _{p(n)} be the exponent of the largest power of p that divides n (that is, the p-adic valuation of n). Then\nu _{p(n!)} = \sum ^{inf ty} _{i =1} \left\lfloor (n)/(p ^{i}) \right\rfloor, where \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 , one has style \left\lfloor (n)/(p ^{i}) \right\rfloor = 0 . This reduces the infinite sum above to\nu _{p(n!)} = \sum ^{L} _{i =1} \left\lfloor (n)/(p ^{i}) \right\rfloor , where L = \lfloor log _{p} n \rfloor .

Example

For n = 6, one has

6 ! = 720 = 2 ^{4} ⋅ 3 ^{2} ⋅ 5 ^{1} . The exponents \nu _{2(6!)} = 4 , \nu _{3(6!)} = 2 and \nu _{5(6!)} = 1 can be computed by Legendre's formula as follows:\begin{align} \nu _{2(6!)} & = \sum ^{inf ty} _{i =1} \left\lfloor (6)/(2 ^{i}) \right\rfloor = \left\lfloor (6)/(2) \right\rfloor + \left\lfloor (6)/(4) \right\rfloor = 3 + 1 = 4 , \\[ 3 pt] \nu _{3(6!)} & = \sum ^{inf ty} _{i =1} \left\lfloor (6)/(3 ^{i}) \right\rfloor = \left\lfloor (6)/(3) \right\rfloor = 2 , \\[ 3 pt] \nu _{5(6!)} & = \sum ^{inf ty} _{i =1} \left\lfloor (6)/(5 ^{i}) \right\rfloor = \left\lfloor (6)/(5) \right\rfloor = 1 . \end{align}

Proof

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 style \left\lfloor (n)/(p) \right\rfloor . 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 \nu _{p(n!)} .

Alternate form

One may also reformulate Legendre's formula in terms of the base-p expansion of n. Let

s _{p(n)} denote the sum of the digits in the base-p expansion of n; then \nu _{p(n!)} = (n - s _{p(n)})/(p -1) . For example, writing n = 6 in binary as 6₁₀ = 110₂, we have that s _{2(6)} = 1 + 1 + 0 = 2 and so \nu _{2(6!)} = (6-2)/(2-1) = 4 . Similarly, writing 6 in ternary as 6₁₀ = 20₃, we have that s _{3(6)} = 2 + 0 = 2 and so \nu _{3(6!)} = (6-2)/(3-1) = 2 .

Proof

Write

n = n _{\ell} p ^{\ell} + … + n _{1} p + n _{0} in base p. Then style \left\lfloor (n)/(p ^{i}) \right\rfloor = n _{\ell} p ^{\ell-i} + … + n _{i+1} p + n _{i} , and therefore\begin{align} \nu _{p(n!) &=} \sum ^{\ell} _{i =1} \left\lfloor (n)/(p ^{i}) \right\rfloor \\ & = \sum ^{\ell} _{i =1} \left(n _{\ell} p ^{\ell-i} + … + n _{i+1} p + n _{i\right)} \\ & = \sum ^{\ell} _{i =1} \sum ^{\ell} _{j = i} n _{j} p ^{j-i} \\ & = \sum ^{\ell} _{j =1} \sum ^{j} _{i =1} n _{j} p ^{j-i} \\ & = \sum ^{\ell} _{j =1} n _{j} ⋅ (p ^{j} -1)/(p -1) \\ & = \sum ^{\ell} _{j =0} n _{j} ⋅ (p ^{j} -1)/(p -1) \\ & = (1)/(p -1) \sum ^{\ell} _{j =0} \left(n _{j} p ^{j} - n _{j\right)} \\ & = (1)/(p -1) \left(n - s _{p(n)\right). \end{align}}

Applications

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

\binom{ 2 n}{n} if and only if n is not a power of 2.

It follows from Legendre's formula that the p-adic exponential function has radius of convergence

p ^{-1/(p-1)} .

References

• • , page 77
• Leonard Eugene Dickson, History of the Theory of Numbers, Volume 1, Carnegie Institution of Washington, 1919, page 263.