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!

6 Responses

  1. Pochiraju says:

    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?’)

    Why?

    • Karishma says:

      Consider 8! = 1*2*3*4*5*6*7*8

      Let’s find the number of 2s in 8!
      8/2 = 4
      4/2 = 2
      2/2 = 1

      Number of 2s = 4+2+1 = 7
      How many 4s can you make with seven 2s? You can make three 4s. (You use six 2s and discard the last one.)

      Now, let’s try to directly find the number of 4s in 8!
      8/4 = 2
      You get only two 4s. Why? Because a 4 you could have made using a 2 from 2 and 2 from 6 is lost. Therefore, it is essential to use this technique with prime numbers.

      You find the number of prime numbers and then put them together to find the number of composite numbers.

  2. Pratap says:

    From above:
    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!

    Not sure if my approach is correct, but here is what i think:
    12= 3×4

    40/3= 13
    13/3=4
    4/3=1
    Total: 18

    Using 4 instead of 2 because the 2 should be used when the dividend is less than 10, this is the limiting condition in my opinion.
    .
    40/4=10
    10/4=2
    Total=12

    Subtract 12 from 18 then half it: (18-12)/2= 3

    Therefore, there are 3 12′s in 40!

    To cross check- 12,24,36 are the three numbers divisible by 12.

    Can you please let me know what your approach is because this could just be a coincidence.

    • Karishma says:

      40! = 1*2*3*4*5*6*7*8*9*10*11*12*13…..*40

      How many 12s can you make? You get a 12 each from 12, 24 and 36. But you can also make more 12s. How? In 40!, you have 3*4 which is 12, you have 2*6 which is 12 etc. The highest power of 12 that you can get from 40! is much more than 3.
      So then how will you get the maximum power of 12? What do you need to make a 12? You need a 3 and two 2s.
      How many 3s are there in 40!? You correctly found it as 18
      How many 2s are there in 40!?
      40/2 = 20
      20/2 = 10
      10/2 = 5
      5/2 = 2
      2/2 = 1
      Total number of 2s = 38
      How many 4s can you make? Two 2s make a 4 so 38/2 = 19
      In 40!, you have 18 3s and 19 4s. You need one 3 and one 4 to make a 12. Since you have only 18 3s, you will be able to make only 18 12s. So highest power of 12 in 40! is 18.

      Quoting: “Using 4 instead of 2 because the 2 should be used when the dividend is less than 10, this is the limiting condition in my opinion.
      .
      Subtract 12 from 18 then half it: (18-12)/2= 3″

      What makes you think this way? You should always use 2 because if you use 4, you miss out on many 2s.
      Why the subtraction?

  3. Pratap says:

    Thanks for the explanation.

    I did not think about the other numbers that can be multiplied to get 12.

    This makes it clearer.

  4. Mike says:

    Hi Karishma

    You are so GOOD. It gives me chill from reading these blogs. THANK YOU SO MUCH!

Leave a Reply

Spam protection by WP Captcha-Free