How to find if a factorial of a number is divisible by a certain number

by Wonder Boy · Published August 3, 2016 · Updated August 3, 2016

You might have solved last year CAT papers(when it was available) or any AIMCAT/SIMCAT/..CAT.

A peculiar type of question that troubles you is whether the factorial of a number is divisible by certain number or not.

The most noticeable thing in the question that you will find is that the number in the denominator is so big that it will make you nervous and once you get nervous, purpose of the test maker is already solved.. haha.. 🙂

So lets discuss today the question type in which factorial is involved.

For e.g. if 240! is completely divisible by 72 ^65 ?

So how do you feel now.. Challenging isn’t it.. But in tests if you don’t know how to solve it, you will feel nervous & will loose some marks.

So lets get down to know the approach to solve this question.

Step 1: Remember that : the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 5 ! = 5 × 4 × 3 × 2 × 1 = 120.

Similarly 240 ! = 240 x 239 x 238 x….x 3 x 2 x 1

Each of these numbers is a multiple of some prime numbers. So if 240! is written as a product of prime numbers.. It will contains lots of 2s, 3s, 5, 7s….. isn’t it.

Step 2: Now we will look at the denominator and try to factorise it.

So 72 = 2^3 x 3^2

Step 3: Lets check the number of 2s & 3s in 240!

Highest power of 2 in 240! = [240/2]+[240/4] + [240/8]+[240/16]+[240/32]+[240/64]+[240/128]

=120 + 60 +30 + 15 + 7 + 3 +1 = 236

So highest power of 2^3 in 240! = [236/3] = 78

Similarly,

Highest power of 3 in 240! = [240/3]+[240/9] + [240/27]+[240/81]

=80 + 26 + 8 + 2 =116

So highest power of 3^2 in 240! = [116/2] =58

Hence the highest power of 72 in 240! is 58.

Therefore 72^65 will not completely divide 240!