Legendre's formula
Lua error in package.lua at line 80: module 'strict' not found.
In mathematics, Legendre's formula gives an expression for the exponent of the largest power of a prime p that divides the factorial . It is named for Adrien-Marie Legendre.
Statement
Let p be a prime and n be a positive integer. Let denote the p-adic valuation of n. Then
where is the floor function. Equivalently, if denotes the sum of the standard base-p digits of n, then
Proof
Since is the product of the integers 1 through n, we obtain at least one factor of p in for each multiple of p in , of which there are Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \textstyle \left\lfloor \frac{n}{p} \right\rfloor . Each multiple of contributes an additional factor of p, each multiple of contributes yet another factor of p, etc. Adding up the number of these factors gives the infinite sum for . The sum contains only finitely many nonzero terms, since Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \textstyle \left\lfloor \frac{n}{p^i} \right\rfloor = 0
for .
To obtain the second form, write in base p. Then Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \textstyle \left\lfloor \frac{n}{p^i} \right\rfloor = n_\ell p^{\ell-i} + \cdots + n_{i+1} p + n_i , and therefore
- Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \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 , we obtain
where is the number of 1s in the binary representation of n.
This can be used to prove that if is a positive integer, then divides Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \binom{2n}{n}
if and only if is not a power of .
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 .
References
- Lua error in package.lua at line 80: module 'strict' not found.
- Lua error in package.lua at line 80: module 'strict' not found., page 77