What is the index of the greatest power of 3 that exactly divides 100!?

June 23, 2019

what is the index of the greatest power of 3 that exactly divides 100!?

33 + (11-1) + (3-1)2 + (1-1)3 = 47

Div with 100 indiv power of 3 and adding

3 = 33
9 = 11
27 = 3
81= 1
total = 48

Two types of questions are very common on factorial.

One, finding out the number of zeros at the end of a factorial expansion. You can find the detailed explanation on how to deal with such questions here.

Two, finding out the largest power of any number that divides any factorial number.
Today, I am going to explain how to approach questions like

Find the largest power of 5 contained in 124!
Find the highest power of 7 that can exactly divide 777!

Let us get started.

Let’s say we have to find out the largest power of 5 contained in 25!
1!, 2!, 3! and 4! are not divisible by 5 because 5 is not a factor in these factorial numbers.

Now if I consider any factorial number greater than 4!, every number consists of 5 or the higher powers of 5.
5!= 1x2x3x4x5
6!= 1x2x3x4x5x6
… …. … …. …
10!= 1x2x3x4x5x6x7x8x9x10
…. …. …. …. …. ….
25!= 1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20x21x22x23x24x25

Multiples of 5 in the expansion of 25! are 5, 10, 15, 20 and 25.

Basically, 25 divided by 5 equals 5. So there are 5 multiples of 5 from 1 to 25.

But, 25=5X5. This means that 25 is giving me an extra 5 which I need to account for. With this logic every multiple of 25 will give me an extra 5.

25 divided by 25 equals 1. So there is 1 multiple of 25 from 1 to 25.

Therefore highest power of 5s in 25! = 25/5+25/25= 5+1 = 6

The same reasoning extends to larger numbers. Suppose we had to find the highest power of 5 in 1000!

There are 1000/5=200 multiples of 5 between 1 and 1000.

The next power of 5 is 25 and there are 1000/25=40 multiples of 25 between 1 and 1000.

The next power of 5 is 5³=125 and each such multiple of 125 gives me still one more extra 5 as compared to other multiples of 25. There are 1000 /125 = 8 such multiples of 125 between 1 and 1000.

The next power of 5 is 5⁴=625 and there is only one multiple of 625 between 1 and 1000, 625 itself.
Hence the total number of 5s in 1000! = 200 + 40 + 8 + 1 = 249.

You keep on dividing with higher powers of the given number till you get 1 as the whole number part. And of course, while adding up we consider only the whole number part and ignore the fractional part.

If you observe, this is nothing but the greatest integer function.
We have to find out the highest power of k that can exactly divide n!.

We divide n by k, n by k², n by k³.. and so on till we get n by k^x equals to 1 or 1 and some decimal part ;(where [P] means the greatest integer less than or equal to P) and then add up.

Highest power of prime number k in n! =[n/k]+[n/k²]+[n/k³]+…….+[n/k^x]; where [P] means the greatest integer less than or equal to P.

Example: Find the highest power of 2 in 50!
Solution: Highest power of 2 in 50! = [50/2]+[50/4]+[50/8]+[50/16]+[50/32]= 25+12+6+3+1= 47

Example: Find the highest power of 30 in 40!
Solution: Express 30 as product of its prime factors. 30=2x3x5. So to make a 30 you need each of 2, 3 and 5. Now in 40! there will be more 2s compared to 3s and more 3s compared to 5s. Hence to extract each 30 out of 40!, we should be bothered only about number of 5s in 40!.

Memory trick: Find number of the largest prime factor of 30 i.e. 5 in 40!.

Highest power of 5 in 40! = [40/5]+[40/25] = 8+1=9.

What if I am asked to find the highest power of numbers like 17, 19 or say 23? Then I will have to deal with numbers like 173,194, 235, etc. Finding the higher powers of such divisors and the subsequent division can be a real pain. So is there an alternate method? Luckily, yes.

Short-cut to find the highest power of a number in a factorial

By now it is clear that we consider only the integral part of the quotient while performing the series of divisions. So we can do this calculation in an easier method. We just divide the number and divide the succeeding quotients by the same number till we get 0. Finally add up all the quotients.