How to find the largest power of a number that divides a factorial number?


Factorial of a number or n! is the product of n consecutive natural numbers starting from 1 to n. Hence, 4! is nothing but 1x2x3x4 = 24

Common Type of Questions on Factorials

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 53=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 54=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 k2, n by k3.. and so on till we get n by kx 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/k2]+[n/k3]+…….+[n/kx]; 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.

In this method we get rid of finding higher powers of the divisor.
So if we have to find the highest power of 5 in 1000!

200+40+8+1= 249. Isn’t this just awesome. I no longer have to worry about the values of higher powers of 5. Also division by 5 is relatively easier than division by 25, 125 or 625.

Share your feedback and let me know if you liked this.

Leave a Reply

Your email address will not be published. Required fields are marked *