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 _{i=1}^{\infty }\left\lfloor {\frac {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 $\textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =0$. This reduces the infinite sum above to

$\nu _{p}(n!)=\sum _{i=1}^{L}\left\lfloor {\frac {n}{p^{i}}}\right\rfloor \,,$

where $L=\lfloor \log _{p}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{aligned}\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{aligned}}$

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

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 {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!)={\frac {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!)={\frac {6-2}{3-1}}=2.$

Proof

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

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 {2n}{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

• 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
• Leonard Eugene Dickson, History of the Theory of Numbers, Volume 1, Carnegie Institution of Washington, 1919, page 263.

External links

• Weisstein, Eric W. "Factorial". MathWorld.