Legendre's formula

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 [math]\displaystyle{ \nu_p(n) }[/math] be the exponent of the largest power of p that divides n (that is, the p-adic valuation of n). Then

[math]\displaystyle{ \nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor, }[/math]

where [math]\displaystyle{ \lfloor x \rfloor }[/math] 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 [math]\displaystyle{ p^i \gt n }[/math], one has [math]\displaystyle{ \textstyle \left\lfloor \frac{n}{p^i} \right\rfloor = 0 }[/math]. This reduces the infinite sum above to

[math]\displaystyle{ \nu_p(n!) = \sum_{i=1}^{L} \left\lfloor \frac{n}{p^i} \right\rfloor \, , }[/math]

where [math]\displaystyle{ L = \lfloor \log_{p} n \rfloor }[/math].

Example

For n = 6, one has [math]\displaystyle{ 6! = 720 = 2^4 \cdot 3^2 \cdot 5^1 }[/math]. The exponents [math]\displaystyle{ \nu_2(6!) = 4, \nu_3(6!) = 2 }[/math] and [math]\displaystyle{ \nu_5(6!) = 1 }[/math] can be computed by Legendre's formula as follows:

[math]\displaystyle{ \begin{align} \nu_2(6!) & = \sum_{i=1}^\infty \left\lfloor \frac 6 {2^i} \right\rfloor = \left\lfloor \frac 6 2 \right\rfloor + \left\lfloor \frac 6 4 \right\rfloor = 3 + 1 = 4, \\[3pt] \nu_3(6!) & = \sum_{i=1}^\infty \left\lfloor \frac 6 {3^i} \right\rfloor = \left\lfloor \frac 6 3 \right\rfloor = 2, \\[3pt] \nu_5(6!) & = \sum_{i=1}^\infty \left\lfloor \frac 6 {5^i} \right\rfloor = \left\lfloor \frac 6 5 \right\rfloor = 1. \end{align} }[/math]

Proof

Since [math]\displaystyle{ n! }[/math] is the product of the integers 1 through n, we obtain at least one factor of p in [math]\displaystyle{ n! }[/math] for each multiple of p in [math]\displaystyle{ \{1, 2, \dots, n\} }[/math], of which there are [math]\displaystyle{ \textstyle \left\lfloor \frac{n}{p} \right\rfloor }[/math]. Each multiple of [math]\displaystyle{ p^2 }[/math] contributes an additional factor of p, each multiple of [math]\displaystyle{ p^3 }[/math] contributes yet another factor of p, etc. Adding up the number of these factors gives the infinite sum for [math]\displaystyle{ \nu_p(n!) }[/math].

Alternate form

One may also reformulate Legendre's formula in terms of the base-p expansion of n. Let [math]\displaystyle{ s_p(n) }[/math] denote the sum of the digits in the base-p expansion of n; then

[math]\displaystyle{ \nu_p(n!) = \frac{n - s_p(n)}{p - 1}. }[/math]

For example, writing n = 6 in binary as 6₁₀ = 110₂, we have that [math]\displaystyle{ s_2(6) = 1 + 1 + 0 = 2 }[/math] and so

[math]\displaystyle{ \nu_2(6!) = \frac{6 - 2}{2 - 1} = 4. }[/math]

Similarly, writing 6 in ternary as 6₁₀ = 20₃, we have that [math]\displaystyle{ s_3(6) = 2 + 0 = 2 }[/math] and so

[math]\displaystyle{ \nu_3(6!) = \frac{6 - 2}{3 - 1} = 2. }[/math]

Proof

Write [math]\displaystyle{ n = n_\ell p^\ell + \cdots + n_1 p + n_0 }[/math] in base p. Then [math]\displaystyle{ \textstyle \left\lfloor \frac{n}{p^i} \right\rfloor = n_\ell p^{\ell-i} + \cdots + n_{i+1} p + n_i }[/math], and therefore

[math]\displaystyle{ \begin{align} \nu_p(n!) &= \sum_{i=1}^{\ell} \left\lfloor \frac{n}{p^i} \right\rfloor \\ &= \sum_{i=1}^{\ell} \left(n_\ell p^{\ell-i} + \cdots + n_{i+1} p + n_i\right) \\ &= \sum_{i=1}^{\ell} \sum_{j=i}^{\ell} n_j p^{j-i} \\ &= \sum_{j=1}^{\ell} \sum_{i=1}^{j} n_j p^{j-i} \\ &= \sum_{j=1}^{\ell} n_j \cdot \frac{p^j - 1}{p - 1} \\ &= \sum_{j=0}^{\ell} n_j \cdot \frac{p^j - 1}{p - 1} \\ &= \frac{1}{p - 1} \sum_{j=0}^{\ell} \left(n_j p^j - n_j\right) \\ &= \frac{1}{p - 1} \left(n - s_p(n)\right). \end{align} }[/math]

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 [math]\displaystyle{ \binom{2n}{n} }[/math] 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 [math]\displaystyle{ p^{-1/(p-1)} }[/math].

References

• Legendre, A. M. (1830), Théorie des Nombres, Paris: Firmin Didot Frères 
• Moll, Victor H. (2012), Numbers and Functions, American Mathematical Society, ISBN 978-0821887950 , page 77
• Leonard Eugene Dickson, History of the Theory of Numbers, Volume 1, Carnegie Institution of Washington, 1919, page 263.

External links

• Weisstein, Eric W.. "Factorial". http://mathworld.wolfram.com/Factorial.html.