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)

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

1. R. Honsberger, In Pólya's Footsteps, MAA, 1999, 229-233.
2. R. Honsberger, Mathematical Gems II, MAA, 1976, 1-10
3. V. H. Moll, Numbers and Functions: From a Classical-Experimental Mathematician's Point of View, AMS, 2012, 76-82
4. 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