# 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

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