Quarter Wit, Quarter Wisdom: The Power in Factorials

Quarter Wit, Quarter WisdomLast week, we started discussing some number properties. Let’s continue that discussion and dive into some more of those. In my opinion, it is the single most important topic on GMAT and one in which the smartest people slip easily. Think of this as a relatively easy way to earn another (or save) 20 or 30 points on your total GMAT score!

Let me show you the concept we will discuss today right away:

QUESTION: If 2^k is a factor of (10!), what is the greatest possible value of k?

(A) 5
(B) 7
(C) 8
(D) 10
(E) 12

SOLUTION:

2^k is a factor of 10! We need to find the maximum value of k. This means that we need to find the total number of 2s in 10!

Let’s begin by writing down 10! to understand the question: 10! = 1*2*3*4*5*6*7*8*9*10

Of the numbers above, the following numbers have 2 as a factor: 2, 4 (two of them), 6, 8 (three of them) and 10

Total number of 2s in 10! is 1 + 2 + 1 + 3 + 1 = 8

Easy enough, right? Yes, it is! Problems arise when we are dealing with relatively bigger numbers, say number of 2s in 40! or 80! etc.

I will now give you a method of solving any such question quickly. Subsequently, I will discuss the logic behind the method.

QUESTION: If 2^k is a factor of (10!), what is the greatest possible value of k?

METHOD:
Step 1: 10/2 = 5 (Divide 10 (obtained from 10!) by 2 (obtained from 2^k))
Step 2: 5/2 = 2 (Divide 5 (obtained from step 1) by 2 and ignore everything after the decimal)
Step 3: 2/2 = 1 (Divide 2 (obtained from step 2) by 2)

Now, the quotient obtained in step 3, i.e. 1, is less than the divisor, i.e. 2, hence stop dividing.

Step 4: Add all the quotients obtained: 5 + 2 + 1 = 8

The greatest possible value of k is 8.

LOGIC:
10! = 1*2*3*4*5*6*7*8*9*10

Each alternate number in the product above will have a 2. Out of 10 numbers, 5 numbers will have a 2. Hence Step 1: 10/2 = 5

These 5 numbers are 2, 4, 6, 8, 10. Each of these numbers give us a 2, therefore we have five 2s as of now.

Now out of these 5 numbers, every alternate number will have another 2 since it will be a multiple of 4. Hence Step 2: 5/2 = 2

These 2 numbers are 4 and 8. Both of these numbers give us another 2, therefore we have two more 2s.Out of these 2 numbers, every alternate number will have yet another 2 because it will be a multiple of 8. Hence Step 3: 2/2 = 1

This single number is 8. It gives us one more 2.

Now, all 2s are accounted for. Just add them 5 + 2 + 1 = 8 (Hence Step 4)

These are the number of 2s in 10!

Similarly, you can find maximum power of any prime number in any factorial.

Let’s quickly run through a few questions to grasp the concept properly.

Question: If 3^k is a factor of (122!), what is the greatest possible value of k?

Solution:

Step 1: 122/3 = 40

Step 2: 40/3 = 13

Step 3: 13/3 = 4

Step 4: 4/3 = 1

Step 5: 40 + 13 + 4 + 1 = 58

Greatest possible value of k is 58.

Question: If 4^k is a factor of (122!), what is the greatest possible value of k?

Solution:

4 is not a prime number but to get the number of 4s in 122!, we can find the number of 2s and half it. (Mind you, it is not the same as finding the number of 4s. Think ‘Why?’)

Step 1: 122/2 = 61

Step 2: 61/2 = 30

Step 3: 30/2 = 15

Step 4: 15/2 = 7

Step 5: 7/2 = 3

Step 6: 3/2 = 1

Step 7: 61 + 30 + 15+ 7 + 3 + 1 = 117

Total number of 2s is 117 so total number of 4s is 58. Greatest possible value of k is 58.

Question: If 6^k is a factor of (40!), what is the greatest possible value of k?

Solution:

6 is not a prime number but we make a 6 by multiplying 2 with 3. To get the number of 6s in 40!, we just need to find the number of 3s because the number of 3s will be fewer than the number of 2s. If you are a little confused, don’t worry. Look at the solution given below.

Let’s find the number of 2s in 40!

Step 1: 40/2 = 20

Step 2: 20/2 = 10

Step 3: 10/2 = 5

Step 4: 5/2 = 2

Step 5: 2/2 = 1

Step 6: 20 + 10 + 5 + 2 + 1 = 38

Total number of 2s is 38.

Let’s find the number of 3s now.

Step 1: 40/3 = 13

Step 2: 13/3 = 4

Step 3: 4/3 =1

Step 4: 13 + 4 + 1 = 18

Total number of 3s is 18.

To make a 6, you need one 2 and one 3. In 40!, you have 38 2s but only 18 3s. So you can make only 18 6s. Therefore, maximum value of k is 18. It is obvious that the total number of a higher prime will be less than the total number of a smaller prime. Hence, you don’t even need to find the number of 2s here.

Usually, the greatest prime number will be the limiting condition, but not always. Think what happens when we need to find the greatest power of 12 in 40!

Karishma, a Computer Engineer with a keen interest in alternative Mathematical approaches, has mentored students in the continents of Asia, Europe and North America. She teaches the GMAT for Veritas Prep in Detroit, and regularly participates in content development projects such as this blog!