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

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$.

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]$$

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!$