Understanding the proof of a formula for $p^e\Vert n!$

This is a proof from a book on number theory I'm reading. I'm having a hard time following. I think there's a variable here that means two different things at two different times...

Theorem:

If n is a positive integer and p is a prime, then $p^e \vert\vert n!$, where $e=\lfloor\frac{n}{p}\rfloor + \lfloor\frac{n}{p^2}\rfloor + \dots + \lfloor\frac{n}{p^r}\rfloor$ and r is determined by n by the inequality $p^r \le n <p^{r+1}$

Proof:

For a given integer k, the multiples of $p^k$ that do not exceed n are $p^k, 2p^k, \cdots, qp^k$ , where q is the largest integer such that $qp^k \le n$. But this says that q is the largest integer not exceeding $n/p^k$, so that $q= \lfloor n/p^k \rfloor$. Thus, $\lfloor n/p^k\rfloor$ gives the number of positive multiples of $p^k$ that do not exceed n.

Interlude:

I understand the proof so far. We've simply chosen some power of p and shown that $\lfloor n/p^k \rfloor$ is the largest integer that we can multiply by $p^k$ and stay under n. Here's where I start to get confused.

Now, if $1 \le m \le n$, then $m=qp^k$ with $(q,p) = 1, 0 \le k \le r$, and m contributes precisely k to the total exponent e with which p appears in the canonical representation of n!

Interlude 2:

How exactly does $m=qp^k$ follow from $1 \le m \le n$? Also, this q seems to mean something other than $\lfloor n/p^k\rfloor$ since we seem to be considering the set of all numbers less than or equal to n and greater than or equal to 1 that have the form $m=qp^k$?

Moreover, m is counted precisely k times by the sum

$\lfloor\frac{n}{p}\rfloor + \lfloor\frac{n}{p^2}\rfloor + \dots + \lfloor\frac{n}{p^r}\rfloor$,

once as a multiple of p, once as a multiple of $p^2$, ... , once as a multiple of $p^k$, and no more. Of course, if $k=0$, then m is not counted in the sum. Therefore, the sum above accounts exactly for the contribution of each m between 1 and n to the exponent e as claimed.

Interlude 3:

What exactly is meant here by counted? I really don't understand the last part of this proof at all...

Solution 1:

Interlude 2. You are considering the numbers of the form $qp^k$ that are between $1$ and $n$, because you are trying to figure out how many multiples of $p^k$ you have in $n!$. $m=qp^k$ does not follow from $1\leq m\leq n$; it is an extra condition. That is, "Let's now look at the numbers of the form $qp^k$ with $\gcd(p,q)=1$ that are between $1$ and $n$."

Interlude 3. In order to figure out the largest power of $p$ that divides $n!$, we need to count how many times $p$ occurs in the prime factorization of $n!$; this is equivalent to counting how many times it occurs in the prime factorizations of each number $m$, $1\leq m\leq n$, and then adding. It will appear once for every multiple of $p$ that is not a multipe of $p^2$; twice for every multiple of $p^2$ that is not a multiple of $p^3$; three times for each multiple of $p^3$ that is not a multiple of $p^4$; etc. But that is hard to count.

Alternatively: once for each multiple of $p$; then one more for each multiple of $p^2$; then one more for each multiple of $p^3$; then one more for each multiple of $p^4$; etc. That's easy to count, because we just figured out exactly how many multiples of $p$, how many multiples of $p^2$, etc. there are between $1$ and $n$.

There are $\lfloor\frac{n}{p}\rfloor$ multiiples of $p$; $\lfloor\frac{n}{p^2}\rfloor$ multiples of $p^2$; $\lfloor \frac{n}{p^3}\rfloor$ multiples of $p^3$; etc. Add them up, we get the number of times $p$ shows up in the factorization.

What they are saying is, instead: focus on a single $m = qp^k$, $\gcd(p,q)=1$. How many times do we count $m$? Once for $p$, once for $p^2$, once for $p^3$, etc. up until we get to $p^k$.

Solution 2:

Maybe the easiest way to follow the proof is to work through a numerical example. What power of 3 divides 100-factorial? Up to 100, the number of multiples of 3 is $[100/3]=33$, and each of these contributes a factor of 3. The number of multiples of $3^2$ is $[100/9]=11$, and each of these contributes an additional factor of 3. The number of multiples of $3^3$ is $[100/27]=3$, and each of these numbers contributes yet one more 3 to the product. Finally, the number of multiples of $3^4$ is $[100/81]=1$, giving yet one more factor of 3. All told, $$[100/3]+[100/9]+[100/27]+[100/81]$$

Solution 3:

This is referred to as Legendre's formula (1830) and is very popular in contest mathematics books. A complete treatment is given in pages 122-128 in Number Theory: Structures, Examples, and Problems by Titu Andreescu and Dorin Andrica.

As in $p$-adic Numbers by Fernando Q. Gouvea, I will refer to the highest exponent with which a prime $p$ divides a nonzero integer $n$ as $v_p(n).$

That is, if $n \equiv 0 \pmod {p^k}$ and $n \neq 0 \pmod {p^{k+1}},$ then we say $v_p(n) = k.$ In particular, A and A define $e_p(n) = v_p(n!)$ and call it Legendre's function. The notation $v_p(n)$ makes a good deal of sense in English language writing, as the function $v_p$ is the "$p$-adic valuation," see page 25 of Gouvea. Ireland and Rosen

denote this by $ \mbox{ord}_p \; n = v_p(n),$ see pages 3-15.

Quoted without proof in How to find maximum $x$ that $k^x$ divides $n!$

So, Theorem 6.5.1 on page 123 of Andreescu and Andrica is $$ e_p(n) = v_p(n!) = \sum_{i \geq 1} \left\lfloor \frac{n}{p^i} \right\rfloor = \frac{n - S_p(n)}{p-1} $$ where $S_p(n)$ is the sum of the digits of $n$ when written in base $p.$

I thought I would prove the middle equality by mathematical induction. We need, for any positive integers $m,n,$

LEMMA:

(A) If $n + 1 \equiv 0 \pmod m,$ then $$ \left\lfloor \frac{n + 1}{m} \right\rfloor = 1 + \left\lfloor \frac{n}{m} \right\rfloor $$ (B) If $n + 1 \neq 0 \pmod m,$ then $$ \left\lfloor \frac{n + 1}{m} \right\rfloor = \left\lfloor \frac{n}{m} \right\rfloor $$

For $n < p,$ we know that $p$ does not divide $n!$ so that $e_p(n) = v_p(n!)$ is $0.$ But all the $\left\lfloor \frac{n}{p^i} \right\rfloor$ are $0$ as well. So the base cases of the induction is true.

Now for induction, increasing $n$ by $1.$ If $n+1$ is not divisible by $p,$ then $e_p(n+1) = e_p(n),$ while part (B) of the Lemma says that the sum does not change.

If $n+1$ is divisible by $p,$ let $v_p(n+1) = k.$ That is, there is some number $c \neq 0 \pmod p$ such that $n+1 = c p^k.$ From the Lemma, part (A), all the $\left\lfloor \frac{n}{p^i} \right\rfloor$ increase by $1$ for $1 \leq i \leq k,$ but stay the same for $i > k.$ So the sum increases by exactly $k.$ But, of course, $e_p(n+1) = v_p((n+1)!) = v_p(n!) + v_p(n+1) = e_p(n) + k.$ So both sides of the middle equation increase by the same $v_p(n+1) = k,$ completing the proof by induction.

Note that it is not necessary to have $n$ divisible by $p$ to get nonzero $e_p(n).$ All that is necessary is that $n \geq p,$ because we are not factoring $n,$ we are factoring $n!$

Solution 4:

One can give a very nice proof using the Von Mangoldt function. We define $\Lambda(n)$, as follows. It equals $\log p$ is $n=p^k$ for some prime $p$; and $0$ else. Observe then that if $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ then $$\log n=\sum_{i=1}^k \alpha_i \log p_i= \sum_{d\mid n}\Lambda (d)$$

The last equality holds by observing we have $\log p$ accounted $\alpha_i$ times for $p^j\mid n,j=1,\ldots,\alpha_i$, and any composite divisor dies. Now, $$\log m!=\sum_{b=1}^m\log b=\sum_{b=1}^m\sum_{d\mid b}\Lambda(d)$$

It suffices we note that $$\sum_{b=1}^m\sum_{d\mid b}\Lambda(d)=\sum_{b=1}^m \sum_{d\geqslant 1}[d\mid b]\Lambda(d)=\sum_{d\geqslant 1}\Lambda(d)\sum_{b=1}^m[d\mid b]$$

and of course $\displaystyle\sum_{b=1}^m[d\mid b]=\left\lfloor \dfrac m d\right\rfloor$, since it counts the number of multiples of $d$ less than $m$. Thus

$$\log m!=\sum_{b=1}^m\log b=\sum_{d\geqslant 1} \Lambda(d)\left\lfloor\frac md \right\rfloor$$

Since the Von Mangoldt function is nonzero only at prime powers, $$\log m!=\sum_{i\geqslant 1}\sum_{p\;\rm prime}\Lambda(p^i)\left\lfloor\frac{m}{p^i}\right\rfloor=\sum_{i\geqslant 1}\sum_{p\;\rm prime}\log p\left\lfloor\frac{m}{p^i}\right\rfloor$$

Hence the result: if we define $v_p(n)=\displaystyle\sum_{i\geqslant 1} \left\lfloor\frac{n}{p^i}\right\rfloor$ $$n!=\prod_{p\rm\; prime}p^{v_p(n)}$$