# What is the logic/theorem/derivation behind finding the exponent of p in n! By [n/p] + [n/p^2] + [n/p^3] + …? [duplicate]

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?

## marked as duplicate by Martin Sleziak, user91500, user940, user147263, Daniel FischerJun 30 '15 at 15:32

• Please explain your notation. In particular, what is E3(100!)? and what is $[x]$ for $x$ a real number? – user37238 Jun 30 '15 at 10:36
• – Martin Sleziak Jun 30 '15 at 12:07

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<p^6<p^7.....$ you won't get any result because $n!$ doesn't contain any higher power of $p$.

However number of steps are totally dependent on $n$ and $p$.
suppose $p$ is prime number $$1,2,3,4,5,...,p,p+1,p+2,....,2p,....3p,3p+1,...,p^2,p^2+1,....2p^2,...p^3,p^3+1,...$$ obviously : every p number has multiple of p
every $p^2$number has multiple of $p^2$
every $p^3$number has multiple of $p^3$
sum of the p multiple is :sum of $$\left \lfloor \frac{n}{p^1} \right \rfloor+\left \lfloor \frac{n}{p^2} \right \rfloor +\left \lfloor \frac{n}{p^3} \right \rfloor +...$$