### Number Theory - 2 more interesting questions on factorial

The idea of factorial is very often
tested in competitive exams. Have given below two interesting questions on this
concept

Questions

1.
How many values can natural number n take, if n! is a multiple of 7

^{6}but not 7^{9}?
2.
How many values can natural number n take, if n! is a multiple of 2

^{20}but not 3^{20}?
Correct
Answers

1.
14 values

2.
21 values

Explanatory
Answers:

1.
How many values can natural number n take, if n! is a multiple of 7

^{6}but not 7^{9}?
The smallest
factorial that will be a multiple of 7 is 7!

14! will be
a multiple of 7

^{2}
Extending
this logic, 42! will be a multiple of 7

^{6}
However,
49! will be a multiple of 7

^{8}as 49 (7 * 7) will contribute two 7s to the factorial. (This is a standard question whenever factorials are discussed). Extending beyond this, 56! will be a multiple of 7^{9}
In general
for any natural number n,

n! will be
a multiple of [n/7] + [n/49] + [n/343] + …..

where [x]
is the greatest integer less than or equal to x. A more detailed discussion of
this is available on this link

So, we see
than 42! is a multiple of 7

^{6}. We also see that 56! is the smallest factorial that is a multiple of 7^{9}. So, n can take values { 42, 43, 44, 45, ……55}
There are
14 values that n can take.

2.
How many values can natural number n take, if n! is a multiple of 2

^{20}but not 3^{20}?
The highest
power of 2 that will divide n! = [n/2] + [n/4] + [n/8] + [n/16]….. and so on.
So, let us try to find the smallest n such that n! is a multiple of 2

^{20},
If n = 10,
the highest power of 2 that will divide n! = [10/2] + [10/4] + [10/8] = 5 + 2 +
1 = 8

If n = 20,
the highest power of 2 that will divide n! = [20/2] + [20/4] + [20/8] + [20/16] = 10 + 5 + 2 + 1 = 18

If n = 24,
the highest power of 2 that will divide n! = [24/2] + [24/4] + [24/8] + [24/16] = 12 + 6 + 3 + 1 = 22

{Here we
can also see that each successive number is just the quotient of dividing the
previous number by 2. As in, [12/2] = 6, [6/2] = 3, [3/2] = 1. This is a
further shortcut one can use.}

So the
lowest number of n such that n! is a multiple of 2^20 is 24

Now, moving
on to finding n! that is a multiple of 3. The highest power of 3 that will
divide n! = [n/3] + [n/9] + [n/27] + [n/81] and so on,

When n =
20, the highest power of 3 that can divide 20! = [20/3] + {6/3] = 6 + 2 = 8

When n = 35,
the highest power of 3 that can divide 35! = [35/3] + {11/3] + [3/3] = 11 + 3 +1
=
15

When n = 45,
the highest power of 3 that can divide 45! = [45/3] + [15/3] + [5/3] = 15 + 5 +1
=
21

The lowest
number n such that n! is a multiple of 3^20 is 45.

When n
takes values from 24 to 44, n! will be a multiple of 2^20 and not 3^20. n can
take 21 values totally.

Labels: CAT number theory, CAT questions

## 0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home