Legendre's Theorem - The Prime Factorization of Factorials
Let \(p\) be a prime and \(x\in\mathbb{Z}, x\ne 0\). The \(\pmb{p}\)-adic valuation of \(\pmb{x}\) - denoted \(\pmb{\nu _{p}(x)}\) - is defined as the largest nonnegative integer \(m\) such that \(p^m\) divides \(x\). In other words, \(\nu _{p}(x)\) is the exact exponent of \(p\) in the prime factorization of \(x\).
Also, by definition, \(\nu _{p}(0)=+\infty\). (It may be observed that the p-adic valuation is the reciprocal of the p-adic norm.)
Theorem (Legendre, 1808)
\(\displaystyle\nu _{p}(n!) = \sum_{k=1}\Big\lfloor\frac{n}{p^k}\Big\rfloor \)
Note that, since sooner or later the growing powers of \(p\) will overtake \(n\), the sum in the theorem is necessarily finite.
Proof
There are \(\displaystyle\Big\lfloor\frac{n}{p}\Big\rfloor \) integers below \(n\) that contribute a factor \(p\). Of these, \(\displaystyle\Big\lfloor\frac{n}{p^2}\Big\rfloor\) contribute a second factor; and among those \(\displaystyle\Big\lfloor\frac{n}{p^3}\Big\rfloor\) contribute a third factor \(p\), and so on.
Corollary
For \(n=p^r\), \(p\) prime, \(\displaystyle\nu _{p}(n!) = \frac{n-1}{p-1}\).
Proof
\(\displaystyle \begin{align} \nu _{p}(n!) &= \Big\lfloor\frac{n}{p}\Big\rfloor + \Big\lfloor\frac{n}{p^2}\Big\rfloor + \ldots + \Big\lfloor\frac{n}{p^{r-1}}\Big\rfloor + \Big\lfloor\frac{n}{p^r}\Big\rfloor \\ &= p^{r-1} + p^{r-2} + \ldots + p + 1 \\ &= \frac{p^{r} - 1}{p - 1} = \frac{n-1}{p-1}. \end{align} \)
Theorem (Legendre, 1808)
Let \(p\) be a prime and let \(n = a_{k}p^{k} + a_{k-1}p^{k-1} + \ldots + a_{1}p + a_{0}\) be the base-\(p\) expansion of \(n\). Then
\(\displaystyle\nu _{p}(n!) = \frac{n - (a_{k} + a_{k-1} + \ldots + a_{1} + a_{0})}{p-1}.\)
If we denote \(s_{p}(n)=a_{k} + a_{k-1} + \ldots + a_{1} + a_{0}\), the sum of all the digits in the expansion of \(n\) in base \(p\), the theorem can be expressed in a more compact form:
\(\displaystyle\nu _{p}(n!) = \frac{n - s_{p}(n)}{p-1}.\)
(Note that, for \(s_{2}{n}\) is just the number of nonzero digits of the binary expansion of \(n\).)
Proof
The important step is to realize that, for \(0\le r\lt k\),
\(\displaystyle \frac{n}{p^{r}} = a_{k}p^{k-r} + a_{k-1}p^{k-1-r} + \ldots + a_{r} + \frac{a_{r-1}p^{r-1}+\ldots + a_{0}}{p^r} \)
Now, in base \(p\) all digits are bounded by \(p-1\), so that
\(\displaystyle \frac{a_{r-1}p^{r-1}+\ldots + a_{0}}{p^r} \le \frac{(p-1)(p^{r-1}+p^{r-2}+\ldots +1)}{p^r} = \frac{p^{r}-1}{p^{r}} \lt 1, \)
implying
\(\displaystyle \Big\lfloor\frac{n}{p^{r}}\Big\rfloor = a_{k}p^{k-r} + a_{k-1}p^{k-1-r} + \ldots + a_{r}. \)
Returning to \(\nu _{p}(n!)\),
\(\displaystyle \begin{align} \nu _{p}(n!) &= \Big\lfloor\frac{n}{p}\Big\rfloor + \Big\lfloor\frac{n}{p^2}\Big\rfloor + \ldots + \Big\lfloor\frac{n}{p^{r-1}}\Big\rfloor + \Big\lfloor\frac{n}{p^r}\Big\rfloor \\ &=\space a_{k}p^{k-1} + a_{k-1}p^{k-2} + \cdots + a_{2}p + a_{1} \\ &\space+ a_{k}p^{k-2} + a_{k-1}p^{k-3} + \cdots + a_{2} \\ &\space\space\space\cdots \\ &\space+ a_{k} \\ &= a_{1}+a_{2}(p+1)+a_{3}(p^{2}+p+1)+\ldots + a_{k}(p^{k-1}+\ldots +1) \\ &= \frac{a_{1}(p-1)+a_{2}(p^{2}-1)+a_{3}(p^{3}-1)+\ldots + a_{k}(p^{k}-1)}{p-1} \\ &= \frac{(a_{0}+a_{1}p+a_{2}p^{2}+a_{3}p^{3}+\ldots + a_{k}p^{k}) - (a_{0}+a_{1}+\ldots +a_{k})}{p-1} \\ &= \frac{n - s_{p}(n)}{p-1}. \end{align} \)
The second theorem sounds especially remarkable for \(p=2\):
The greatest power of \(2\) dividing \(n!\) is \(2^{n-r}\) where \(r\) is the number of \(1\)s in the binary expansion of \(n\).
Legendre's theorem should be in the toolkit of every aspiring math olympian. Here are several application [Mihet]:
\(2^n\) never divides \(n!\), \(n\gt 0\).
\(2^{n-1}\) divides \(n!\), iff \(n\) is a power of \(2\).
We know (Corollary above) that, for \(n=2^k\), \(\nu _{2}(n!)=n-1\). On the other hand, \(s_{2}(n)=1\) only when \(n\) has a single \(1\) in its binary expansion, i.e., when \(n\) is a power of \(2\).
There are infinitely many integer \(n\) such that \(n-\nu_{2}(n)=2013.\)
(Any \(n\) whose binary expansion contains \(2013\) \(1\)s serves the purpose.)
Here's the only known portrait of Adrien-Marie Legendre (1752-1833) which is a caricature by J.-L. Boilly.
References
- R. Honsberger, In Pólya's Footsteps, MAA, 1999, 229-233.
- R. Honsberger, Mathematical Gems II, MAA, 1976, 1-10
- V. H. Moll, Numbers and Functions: From a Classical-Experimental Mathematician's Point of View, AMS, 2012, 76-82
- D. Mihet, Legendre's and Kummer's Theorems Again, Resonance, v 15, n 12 (December 2010), Indian Academy of Sciences & Springer, 1111-1121
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
71930918