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 for Adrien-Marie Legendre.

Statement

Let p be a prime and n be a positive integer. Let $\nu_p(n)$ denote the p-adic valuation of n. Then

$\nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor,$

where $\lfloor x \rfloor$ is the floor function. Equivalently, if $s_p(n)$ denotes the sum of the standard base-p digits of n, then

$\nu_p(n!) = \frac{n - s_p(n)}{p - 1}.$

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, \dots, n\}$, of which there are $\textstyle \left\lfloor \frac{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!)$. The sum contains only finitely many nonzero terms, since $\textstyle \left\lfloor \frac{n}{p^i} \right\rfloor = 0$ for $p^i > n$.

To obtain the second form, write $n = n_\ell p^\ell + \cdots + n_1 p + n_0$ in base p. Then $\textstyle \left\lfloor \frac{n}{p^i} \right\rfloor = n_\ell p^{\ell-i} + \cdots + n_{i+1} p + n_i$, and therefore

$\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}$

Examples

For $p = 2$, we obtain

$\nu_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 $\binom{2n}{n}$ if and only if $n$ is not a power of $2$.

Applications

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

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, MR 2963308, page 77

External links

• Wolfram MathWorld entry on the factorial function