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⁶ but not 7⁹?

2. How many values can natural number n take, if n! is a multiple of 2²⁰ but not 3²⁰?

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⁶ but not 7⁹?

The smallest factorial that will be a multiple of 7 is 7!

14! will be a multiple of 7²

Extending this logic, 42! will be a multiple of 7⁶

However, 49! will be a multiple of 7⁸ 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⁹

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⁶. We also see that 56! is the smallest factorial that is a multiple of 7⁹. 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²⁰ but not 3²⁰?

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²⁰,

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.