elementary number theory - What is the logic/theorem/derivation behind finding the exponent of p in n! By [n/p] + [n/p^2] + [n/p^3] + ....?

The exponent of prime number of 3 in 100! is 48. It means 100! is divisible by $3^48$

$$E_3(100!) = \left\lfloor\frac{100}3\right\rfloor + \left\lfloor\frac{100}{3^2}\right\rfloor + \left\lfloor\frac{100}{3^3}\right\rfloor + \left\lfloor\frac{100}{3^4}\right\rfloor = 33+11+3+1 = 48$$ What is the derivation/math behind the above logic?

Answer

Think in this way....

If $p$ is a prime number, actually you want to calculate what is the highest power of $p$ that divides exactly some number $n$. Let $n=100$ & $p=3$ in your case.

1st step: Look for multiple of $p$ through the $n!$

$p, 2p,3p,...$ and in order to get how many multiple of $p$, just divide $n/p$ and take integer part of it.

Example: $3, 6, 9, 12, 15,18,..,99$ will contain at least one power of $3$

2nd step:Look for the multiple of $p^2$.why? because it is the first number in $n!$ which contain exactly two powers of $p$, if $p^2<=n$.

$p^2, 2p^2,3p^2,...$ and in order to get how many multiple of $p^2$, just divide $n/p^2$ and take integer part of it.

Example: $9, 18, 27,...,99$ will contain at least two powers of $3$.

3rd step:Look for the multiple of $p^3$.why? because it is the first number in $n!$ which contain exactly three powers of $p$, if $p^3<=n$.

$p^3, 2p^3,3p^3$ and in order to get how many multiple of $p^3$, just divide $n/p^3$ and take integer part of it.

Example: $27,54,81$ will contain at least three powers of $3$.

4th step:Look for the multiple of $p^4$.why? because it is the first number in $n!$ which contain exactly four powers of $p$, if $p^4<=n$.

$p^4$ and in order to get how many multiple of $p^4$, just divide $n/p^4$ and take integer part of it.

Example: $81$ will contain at least four powers of $3$.

>=5 steps:since $p^5>n$ and so for highest power of $p$ because $p^5

Final answer is: Ans(step1+step2+step3+step4).

However number of steps are totally dependent on $n$ and $p$.