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$.
No comments:
Post a Comment