State/Canonical decompositions of binomial coefficients

From SlugmathWiki

Proposition
Proof

Proposition: (Canonical decompositions of binomial coefficients) Suppose that $n,k \in \NN$, $n \geq 1$, and $0 \leq k \leq n$. Let $e_p$ be the exponent of $p$ in the canonical decomposition of $\left( {n \atop k} \right)$ into primes. Then, $$e_p = \sum_{i=0}^{\lfloor log_p(n) \rfloor} \lfloor \frac{n}{p^i} \rfloor - \left( \lfloor \frac{k}{p^i} \rfloor + \lfloor \frac{n-k}{p^i} \rfloor \right).$$ Furthermore, this exponent satisfies the inequality: $$0 \leq e_p \leq \lfloor log_p(n) \rfloor.$$

Logical Connections

This statement logically relies on the following definitions and statements: Def/Canonical decomposition into primes, State/Canonical decompositions of factorials, State/The floor sum identity

The following statements and definitions rely on the material of this page:

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 binomial coefficients

From SlugmathWiki

Logical Connections

Views

Personal tools

Navigation

Mathematics

Pegagogy

Search

Toolbox

	Suppose that $n,k \in \NN$, $n \geq 1$, and $0 \leq k \leq n$. Let $e_p$ be the exponent of $p$ in the canonical decomposition of $\left( {n \atop k} \right)$ into primes.
	Recall that: $$\left( {n \atop k} \right) = \frac{n!}{k!(n-k)!}.$$ Recall that the exponent of $p$ in the canonical decomposition of $n!$ is given by: $$\sum_{i=0}^{\lfloor log_p(n) \rfloor} \lfloor \frac{n}{p^i} \rfloor.$$ It follows that: $$e_p = \sum_{i=0}^{\lfloor log_p(n) \rfloor} \lfloor \frac{n}{p^i} \rfloor - \left( \lfloor \frac{k}{p^i} \rfloor + \lfloor \frac{n-k}{p^i} \rfloor \right).$$ By the floor sum identity, we have: $$ \lfloor \frac{n}{p^i} \rfloor - \left( \lfloor \frac{k}{p^i} \rfloor + \lfloor \frac{n-k}{p^i} \rfloor \right) \in \{0,1 \}.$$ Hence, $e_p$ is bounded by the number of terms in the sum.
	$0 \leq e_p \leq \lfloor log_p(n) \rfloor$.