Algebra Solutions: A formula for the largest power of a prime dividing a factorial

Let $p$ be a prime and $n \in \mathbb{Z}^+$ . Find a formula for the largest power of $p$ which divides $n!$ .

Before attacking this problem, we prove the following lemma.
Lemma: Let $a,b \in \mathbb{Z}^+$ . The number of multiples of $a$ which are less than or equal to $b$ is $\lfloor \frac{b}{a} \rfloor$ .
Proof: Note first that $\lfloor \frac{b}{a} \rfloor$ is precisely the quotient part returned by the Euclidean algorithm on $b$ and $a$ , since if $b = qa + r$ where $0 \leq r < a$ , then $\frac{b}{a} = q + \frac{r}{a}$ , so $q = \lfloor \frac{b}{a} \rfloor$ . Then we have $ka \leq b$ for precisely $1 \leq k \leq q$ . $\square$
Now for the main problem. Our goal is to find a formula that gives the largest power of $p$ which divides $n!$ ; equivalently, to find the number of times $p$ appears in the factorization of $n!$ . Note that there will be one $p$ factor for each multiple of $p$ less than $n$ – that is, $\lfloor \frac{n}{p} \rfloor$ . This does not account for all of the factors, though; multiples of $p^2$ contribute one more each, for a total of $\lfloor \frac{n}{p^2} \rfloor$ . We can continue for higher powers of $p$ ; for each $k \in \mathbb{Z}^+$ we count an additional $\lfloor \frac{n}{p^k} \rfloor$ factors. Note that every $p$ factor is counted. Moreover, no factor is counted more than once. Thus, the highest power of $p$ which divides $n$ is $p^M$ , where $M = \sum_{k \in \mathbb{Z}^+} \lfloor \frac{n}{p^k} \rfloor$ . Note that for sufficiently large $k$ , $\lfloor \frac{n}{p^k} \rfloor = 0$ , so that the summation indeed converges. $\blacksquare$

Algebra Solutions

A formula for the largest power of a prime dividing a factorial

No comments:

Post a Comment