State/Canonical decompositions of factorials

From SlugmathWiki

Proposition
Proof

Proposition: (Canonical decompositions of factorials) Suppose that $n \in \NN$. Let $(e_p)$ be the sequence of exponents in the canonical decomposition of $n!$ into primes. Then, $$e_p = \sum_{i=1}^{\lfloor log_p(n) \rfloor} \lfloor \frac{n}{p^i} \rfloor.$$

Logical Connections

This statement logically relies on the following definitions and statements: Def/Canonical decomposition into primes, Def/Factorial, State/Counting multiples of d between 1 and n

The following statements and definitions rely on the material of this page: State/Canonical decompositions of binomial coefficients

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Basic number theory

State/Canonical decompositions of factorials

From SlugmathWiki

Logical Connections

Views

Personal tools

Navigation

Mathematics

Pegagogy

Search

Toolbox

	Suppose that $n \in \NN$, and let $(e_p)$ be the sequence of exponents in the canonical decomposition of $n!$ into primes.
	Consider a prime number $p$. If $1 \leq i \leq n$, define $e_p(i)$ to be the exponent of $p$ in the canonical decomposition of $i$ into primes. Since $n! = \prod_{i=1}^n i$, we find that: $$e_p = \sum_{i=1}^n e_p(i).$$ For all $j \in \NN$, define: $$M(j) = \{ i \in \NN \mbox{ such that } 1 \leq i \leq n \mbox{ and } p^j \mbox{ divides } i \}.$$ Observe that: $$i \in M(j) - M(j+1) \Leftrightarrow e_p(i) = j.$$ Hence, we find that: $$e_p = \sum_{i=1}^n e_p(i) = \sum_{j=1}^n \vert M(j) - M(j+1) \vert j.$$ Since $M(j) \supset M(j+1)$, we find that: $$\vert M(j) - M(j+1) \vert = \vert M(j) \vert - \vert M(j+1) \vert.$$ Hence, we find that $$e_p = \sum_{j=1}^\infty \vert M(j) \vert j - \vert M(j+1) \vert \vert j.$$ By "telescoping", we find that: $$e_p = \sum_{j=1}^\infty \vert M(j) \vert j - \sum_{j=2}^\infty \vert M(j) \vert (j-1).$$ $$e_p = \sum_{j=1}^\infty \vert M(j) \vert (j - (j-1)) = \sum_{j=1}^\infty \vert M(j) \vert.$$ By counting multiples of $p^j$, we find that: $$e_p = \sum_{j=1}^\infty \lfloor \frac{n}{p^j} \rfloor.$$ Here, all of the terms are zero, except when $p^j \leq n$. It follows that:
	$$e_p = \sum_{i=1}^{\lfloor log_p(n) \rfloor} \lfloor \frac{n}{p^i} \rfloor.$$