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

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

Weisstein, Eric W. "Factorial". MathWorld.

This article is issued from Wikipedia - version of the 10/24/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.