ISI2019-MMA-1

Question

The highest power of $7$ that divides $100!$ is : 

• A. $14$
• B. $15$
• C. $16$
• D. $18$

Answer 1

$\lfloor \frac{100}{7} \rfloor$ + $\lfloor  \frac{100}{7^2}\rfloor$ + $\lfloor  \frac{100}{7^3}\rfloor$ +....

= 14 + 2 + 0 + ....

 = 16

Answer is C

Comments

is it direct formula?

---

Yes @srestha , if p is a prime number , then the highest power of p in a factorial of n is given by 

$\frac{n}{p}$ + $\frac{n}{p^2}$ + $\frac{n}{p^3}$ + ....

---

what is more important is how this formula is derived? It is a great brain teasing exercise to derive this formula :)

---

yes, do u got the logic??

---

Can you explain your logic behind this formula ?

---

@s_dr_13

Let us look at this example..

we have to count the number of 5's in the product $1*2*3*4....*999*1000$ to get the power of 5.

step 1:

$\left \lfloor 100/5 \right \rfloor=200$ gives the number of integers between 1 and 1000 that has 5 as their divisor.

i.e gives the cardinality of set$\{5,10,15,20,25.....995,1000\}$ each of these numbers contribute a 5 to the product $1*2*3*4....*999*1000$

step 2:

$\left \lfloor 1000/5^{2} \right \rfloor=40$ gives the number of integers between 1 and 1000 that have 25 as their divisor.

i.e gives the cardinality of set $\{25,50,75.....975,1000\}$.Each of these numbers contribute two 5's to the product.

But the thing to note is ,we have already counted one 5 for each integer in the step 1.So on total,each element of set contributes only one 5 for the product.

Step 3:

$\left \lfloor 1000/5^{3} \right \rfloor=8$ gives the number of integers between 1 and 1000 that contribute three 5's to the product.

i.e gives the cardinality of set $\{125,250,375.....875,1000\}$.Each of these numbers contribute three 5's to the product.

But we have already counted one 5 for each integer in step 1 and one 5 for each integer in step 2.

So on total, each element of set contributes only one 5 for the product.

Step 5:

similarly, $\left \lfloor 1000/5^{4} \right \rfloor=1$ gives the cardinality of set $\{625\}$ which has 625 as their divisor.

i.e 625 contributes four 5's to the product..

But we have counted three 5's in each of step 1,step 2,step3.So essentially 625 contributes only one 5 to the product.

The below diagram represents what we have done till now... one 5 striked off means one 5 is counted..

$\{5,10,15,20,25.....995,1000\}$,$\{25,50,75.....975,1000\}$,$\{125,250,375.....875,1000\}$,$\{625\}$

So to be short, each element of the above sets contributes one 5 to the product $1*2*3...*999*1000$

whose cardinality is given by  $\left \lfloor 1000/5 \right \rfloor$, $\left \lfloor 1000/5^{2} \right \rfloor$, $\left \lfloor 1000/5^{3} \right \rfloor$, $\left \lfloor 1000/5^{4} \right \rfloor$ respectively...

similarly we can work for other examples..

Let me know if you have any doubts.. Even iam not satisfied with my explanation :(