2
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

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$
and so on
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 +...$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.