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

${\nu }_p(n!)=\sum _{i=1}^L\lfloor \frac{n}{p^i}\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{array}{rl}{\nu }_2(6!)& =\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{6}{2^i}\rfloor =\lfloor \frac{6}{2}\rfloor +\lfloor \frac{6}{4}\rfloor =3+1=4,\\ {\nu }_3(6!)& =\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{6}{3^i}\rfloor =\lfloor \frac{6}{3}\rfloor =2,\\ {\nu }_5(6!)& =\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{6}{5^i}\rfloor =\lfloor \frac{6}{5}\rfloor =1.\end{array}$

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 $\lfloor \frac{n}{p}\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 $\lfloor \frac{n}{p^i}\rfloor =n_{\ell }{p}^{\ell -i}+\cdots +n_{i+1}p+n_i$, and therefore

$\begin{array}{rl}{\nu }_p(n!)& =\sum _{i=1}^{\ell }\lfloor \frac{n}{p^i}\rfloor \\ & =\sum _{i=1}^{\ell }(n_{\ell }{p}^{\ell -i}+\cdots +n_{i+1}p+n_i)\\ & =\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 }(n_j{p}^j-n_j)\\ & =\frac{1}{p-1}(n-s_p(n)).\end{array}$

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 $(\genfrac{}{}{0ex}{}{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.