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

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: