Q:

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

A:

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

A:

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

A:

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

