Today I was studying a correctness proof of an algorithm, and in one of the proof steps and did not understand what was written.
Be $p$ and $n \in N$ ($N$ is the set of naturals numbers), where $p$ is a prime. The property bellow is the property I couldn't understand.
$argmax_{i \in N} (p^i : p^i | n!) = \sum_{j = 1}^{\infty} \lfloor \frac{n}{p^j} \rfloor$
That is, $i$ (the greatest exponent of $p$ such that $p^i | n!$) is equals to $\sum_{j = 1}^{\infty} \lfloor \frac{n}{p^j} \rfloor$.
If someone is interested in consulting the problem, and the solution explanation.
Thank you.
Assuming I'm reading the question correctly, you're asking why you can calculate the highest power of $p$ that divides $n!$ as $$ \sum_{j = 1}^{\infty} {\left\lfloor \frac{n}{p^j} \right \rfloor} $$
Let's look at a specific example and it should clear how to extend it to the general case.
Imagine we are trying to find the highest power of $5$ that divides $300!$. We begin writing out the first few factors: $$ 1 \quad 2 \quad 3 \quad 4 \quad \color{red}5 \quad 6 \quad 7 \quad 8 \quad 9 \quad \color{red}{10} \quad 11 \quad 12 \quad 13 \quad 14 \quad \color{red}{15} \quad \cdots $$
Notice that only the red numbers here contribute a factor of $5$ to the factorial product. Each of these contributes a single factor of $5$... at least. You'll notice that $$ \begin{align} 1 \times \color{red}5 &= 5 \\\\ 2 \times \color{red}5 &= 10 \\\\ 3 \times \color{red}5 &= 15 \\\\ 4 \times \color{red}5 &= 20 \\\\ \color{red}5 \times \color{red}5 &= 25 \end{align} $$
Uh oh, the number $25$ contributes two total factors of $5$ because it is $5^2$. On top of that, notice all of the following numbers \begin{align} 1 \times \color{red}{25} &= 25 \\\\ 2 \times \color{red}{25} &= 50 \\\\ 3 \times \color{red}{25} &= 75 \\\\ 4 \times \color{red}{25} &= 100 \\\\ \cdots \end{align} similarly contribute two factors. Continuing in this way, we can see that $5^3 = 125$ contributes three total factors, and so on.
We can now count these up by first counting all of the multiples of $5$, which is ${\left\lfloor \frac{300}{5} \right \rfloor} = 60$.
Next, we count all of the multiples of $5^2 = 25$ as there's a second factor we need to account for, which is ${\left\lfloor \frac{300}{5^2} \right \rfloor} = 12$.
Continuing: the multiples of $5^3 = 125$ as there's a second factor we need to account for, which is ${\left\lfloor \frac{300}{5^3} \right \rfloor} = 2$.
Technically, we should go on further, but all of the terms will be $0$ at some point: multiples of $5^4$ is ${\left\lfloor \frac{300}{5^4} \right \rfloor} = 0$.
Add all of these numbers together to get the final answer of $60+12+2 = 74$.
Replace $n$ to generalize, write in summation notation, and we have our formula: $$ \sum_{j = 1}^{\infty} {\left\lfloor \frac{n}{p^j} \right \rfloor} $$