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 $\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_^ \left\lfloor \frac \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 $\textstyle \left\lfloor \frac \right\rfloor = 0$. This reduces the infinite sum above to
:$\nu_p(n!) = \sum_^ \left\lfloor \frac \right\rfloor \, ,$
where $L = \lfloor \log_ n \rfloor$.

Example

For ''n'' = 6, one has $6! = 720 = 2^4 \cdot 3^2 \cdot 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
\nu_2(6!) & = \sum_^\infty \left\lfloor \frac 6 \right\rfloor = \left\lfloor \frac 6 2 \right\rfloor + \left\lfloor \frac 6 4 \right\rfloor = 3 + 1 = 4, \\ pt\nu_3(6!) & = \sum_^\infty \left\lfloor \frac 6 \right\rfloor = \left\lfloor \frac 6 3 \right\rfloor = 2, \\ pt\nu_5(6!) & = \sum_^\infty \left\lfloor \frac 6 \right\rfloor = \left\lfloor \frac 6 5 \right\rfloor = 1.
\end

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 $\$, of which there are $\textstyle \left\lfloor \frac \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!) = \frac.$

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!) = \frac = 4.$
Similarly, writing 6 in ternary as 6₁₀ = 20₃, we have that $s_3(6) = 2 + 0 = 2$ and so
:$\nu_3(6!) = \frac = 2.$

Proof

Write $n = n_\ell p^\ell + \cdots + n_1 p + n_0$ in base ''p''. Then $\textstyle \left\lfloor \frac \right\rfloor = n_\ell p^ + \cdots + n_ p + n_i$, and therefore
:$\begin \nu_p(n!) &= \sum_^ \left\lfloor \frac \right\rfloor \\ &= \sum_^ \left(n_\ell p^ + \cdots + n_ p + n_i\right) \\ &= \sum_^ \sum_^ n_j p^ \\ &= \sum_^ \sum_^ n_j p^ \\ &= \sum_^ n_j \cdot \frac \\ &= \sum_^ n_j \cdot \frac \\ &= \frac \sum_^ \left(n_j p^j - n_j\right) \\ &= \frac \left(n - s_p(n)\right). \end$

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$ 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^$.

References

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

External links

*{{MathWorld, Factorial, Factorial

Factorial and binomial topics