CAT Practice : Number System: Factorial

You are here: Home  CAT Questionbank   CAT Quant  Number System: Factorial  Question 6
Finding highest power of a prime that divides any factorial is easy. How do we find the highest power of a composite number that divides a specific factorial

Factorials - basic

Q.6: What is the highest power of 12 that divides 54!?
1. 25
2. 26
3. 30
4. 4

Choice A. 25

Detailed Solution

12 = 22 * 3, so we need to count the highest power of 2 and highest power of 3 that will divide 54! and then we can use this to find the highest power of 12.

The method to find highest powers of 2 and 3 are similar to the one outlined in the previous question.

Highest power of 2 that divides 54! = $\left[ {{{{\rm{54}}} \over {\rm{2}}}} \right]{\rm{ + }}\left[ {{{{\rm{54}}} \over {\rm{4}}}} \right]{\rm{ + }}\left[ {{{{\rm{54}}} \over {\rm{8}}}} \right]{\rm{ + }}\left[ {{{{\rm{54}}} \over {{\rm{16}}}}} \right]{\rm{ + }}\left[ {{{{\rm{54}}} \over {{\rm{32}}}}} \right]$ = 27 + 13 + 6 + 3 + 1 = 50
Highest power of 3 that divides 54! = $\left[ {{{{\rm{54}}} \over {\rm{3}}}} \right]{\rm{ + }}\left[ {{{{\rm{54}}} \over {\rm{9}}}} \right]{\rm{ + }}\left[ {{{{\rm{54}}} \over {{\rm{27}}}}} \right]$ = 18 + 6 + 2 = 26

Or 54! is a multiple of 250 * 326. Importantly, these are the highest powers of 2 and 3 that divide 54!.
22 * 3 = 12. We need to see what is the highest power of 22 * 3 that we can accommodate within 54!

In other words, what is the highest n such that (22 * 3)n can be accommodated within 250 * 326.

Let us try some numbers, say, 10, 20, 30

(22 * 3)10 = 220 * 310, this is within 250 * 326
(22 * 3)20 = 240 * 320, this is within 250 * 326
(22 * 3)30 = 260 * 330, this is not within 250 * 326

The highest number possible for n is 25.
(22 * 3)25 = 250 * 325, this is within 250 * 326, but (22 * 3)26 = 252 * 326, this is not within 250 * 326.

So, 54! can be said to be a multiple of (22 * 3)25. Or, the highest power of 12 that can divide 54! is 25.

Note: For most numbers, we should be able to find the limiting prime. As in, to find the highest power of 10, we need to count 5s. For the highest power of 6, we count 3s. For 15, we count 5s. For 21, we count 7’s. However, for 12, the limiting prime could be 2 or 3, so we need to check both primes and then verify this.

Our Online Course, Now on Google Playstore!

Fully Functional Course on Mobile

All features of the online course, including the classes, discussion board, quizes and more, on a mobile platform.

Cache Content for Offline Viewing

Download videos onto your mobile so you can learn on the fly, even when the network gets choppy!

More questions from Number System - Factorial

This idea is so good that it comes with an exclamation mark. N! holds marvels that you might not have noticed before. Enter here to see those.