Welcome to the penultimate article in our series on exponents on the GMAT/Executive Assessment (EA). Today we explore a problem category in which exponents are used to notating the highest power of an integer by which a larger integer is divisible. GMAT/EA problems typically use the variable k in the place of this exponent. These problems involve exponents but are also in the realm of number properties. Exponents are useful for notating the numbers of prime factors of a given integer. Here’s an example:
4680
468 * 10
234 * 2 * 2 * 5
117 * 2 * 2 * 2 * 5
13 * 9 * 2 * 2 * 2 * 5
13 * 3 * 3 * 2 *2 * 2 * 5
23 * 32 * 5 * 13
Since exponents notate successive multiplications by the same number, we can use them to consolidate lists of prime factors and immediately see how many of each prime factor exists within a number like 4680.
13 * 3 * 3 * 2 *2 * 2 * 5
23 * 32 * 5 * 13
In this example, 23 is a factor of 4680, but 24 is not a factor of 4680 because 4680 has only three prime factors of 2. 32 is a factor of 4680, but 33 is not a factor of 4680 because 4680 has only two prime factors of 3. A GMAT/EA problem might ask something like this: “What is the greatest integer k for which 2k is a factor of 4680?” The answer to this problem would be 3.
Let’s take a look at an official problem:
If p is the product of the integers from 1 to 30, inclusive, what is the greatest integer k for which 3k is a factor of p?
(A) 10
(B) 12
(C) 14
(D) 16
(E) 18
This question effectively asks, “How many prime factors of 3 are in the number p?” The number p is “the product of the integers from 1 to 30 inclusive.” This is the verbalization of a piece of notation called the factorial. Factorials notate the multiplication of a positive integer by each positive integer less than itself. Here are some examples:
4! = 4 * 3 * 2 * 1
7! = 7 * 6 * 5 * 4 * 3 * 2 * 1
9! = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
To generalize the formula:
n! = n * (n – 1) * (n – 2) * . . . * 1
Because the 1 at the end of the multiplication does not affect the value, factorials are often “spelled out” without the 1 at the end of the list.
Obviously, 30! Is too large of a number for us to evaluate. As a general rule, finding the actual value of any factorial larger than 7! or so is a waste of time. We are almost always more interested in the factors contained within a factorial.
30! = 30 * 29 * 28 * . . . * 1
So how many prime factors of 3 are contained within (30!)? Well, numbers like 29 and 28 don’t contain any prime factors of 3, because these numbers are not multiples of 3. The only factors of 30! that contain prime factors of 3 are the multiples of 3.
30 27 24 21 18 15 12 9 6 3
Some of these factors themselves contain more than one prime factor of 3. 27 is 33, so it has 3 threes. 9 is 32, so it has 2 threes. And a sneaky one is 18, which is not a power of 3 but is 2 * 9, or 2 * 32. So 18 also has 2 threes.
We can tally up all our prime factors of 3 like this:
30 27 24 21 18 15 12 9 6 3
1 3 1 1 2 1 1 2 1 1
If we add up the values in the second row, we obtain an answer of 14 prime factors of 3 in the number (30!). The correct answer is C.
This approach works, but there is actually a more straightforward way involving division. Consider first that performing the division a/b is effectively a way of counting how many multiples of b are less than or equal to a. 80 / 10 = 8, so 8 multiples of 10 are less than or equal to 80. 70 / 14 = 5, so 5 multiples of 14 are less than or equal to 70. When a is not perfectly divisible by b, the quotient still gives the number of multiples of b that are less than or equal to a, and the remainder is irrelevant. 56 / 9 = 6 remainder 2, so there are 6 multiples of 9 less than or equal to 56).
How does this help us identify prime factors of 3 in a number like (30!)? Well, if we take the quotient of 30/3, we can see how many of the factors of 30! are multiples of 3. In this case, there are 10. So there are at least 10 prime factors of 3 in the number (30!). If we take the quotient of 30/9 (or 30/(32), we see that 3 of these 10 multiples of 3 are also multiples of 9. Each of these numbers (9, 18, and 27) contains another prime factor of 3 that we did not “count” when we performed the division 30/3. Finally, we need to take 30/27 (or 30/33) to see that one of our 3 multiples of 9 is also a multiple of 27. The number, of course, is 27 itself, which contains a third prime factor of 3 that we didn’t “count” when we performed the divisions 30/3 and 30/9.
quotient of 30 / 3 = 10
quotient of 30 / 9 = 3
quotient of 30 / 27 = 1
10 + 3 + 1 = 14 prime factors of 3 within 30!
To find the highest integer k for which nk is a factor of t!, add up the quotients of t/n, t/(n2), t/(n3) . . . for every power of n that is less than or equal to t.
Here’s one that requires some extra steps of algebra:
If n = 9! – 64, which of the following is the greatest integer k such that 3k is a factor of n?
(A) 1
(B) 3
(C) 4
(D) 6
(E) 8
This question effectively asks, “How many prime factors of 3 are in the number 9! – 64?”
Let’s start by viewing 9! and 64 in factored forms:
9! – 64
(9 * 8 * 7 * 6 * 5 * 4 * 3 * 2) – (6 * 6 * 6 * 6)
We can go one step further and break all the non-primes down to primes:
(9 * 8 * 7 * 6 * 5 * 4 * 3 * 2) – (6 * 6 * 6 * 6)
(3 * 3) * 23 * 7 * (2 * 3) * 5 * 22 * 3 * 2 – (24 * 34)
Since each factor of 6 in 64 is equal to (3 * 2), we can represent the group of 4 sixes as (24 * 34). Now to consolidate the rest:
(3 * 3) * 23 * 7 * (2 * 3) * 5 * 22 * 3 * 2 – (24 * 34)
(27 * 34 * 5 * 7) – (24 * 34)
The subtraction is preventing us from seeing how many threes are in the integer version of this number. We will have to extract a factor of (24 * 34), like this:
(27 * 34 * 5 * 7) – (24 * 34)
(24 * 34)[(23 * 5 * 7) – 1]
Now we can evaluate the bracketed expression in order to prime factorize again:
(24 * 34)[(23 * 5 * 7) – 1]
(24 * 34)[(8 * 5 * 7) – 1]
(24 * 34)[280 – 1]
(24 * 34)(279)
And we’ll break 279 down into prime factors:
(24 * 34)(279)
(24 * 34)(9 * 31)
(24 * 34)(32 * 31)
24 * 36 * 31
Finally we can see that there are 6 prime factors of 3 in the number 9! – 64, and the correct answer is D.
Here’s a final problem for today:
For the positive integers a, b, and k, ak| |b means that ak is a divisor of b but a(k+1) is not a divisor of b. If k is a positive integer and 2k| |72, then k is equal to
(A) 2
(B) 3
(C) 4
(E) 8
(D) 18
This problem uses a random symbol – two vertical lines – and then defines it for you. This is common practice on GMAT/EA problems and is simply a way to “disguise” the type of problem you’re looking at. Think about the way they’ve defined this symbol, and you’ll see that this problem is asking the same thing as our other examples: what is the greatest integer k for which 2k is a factor of 72? Or to put it even more simply: How many prime factors of 2 does 72 have?
72 = 8 * 9 = 23 * 32
There are 3 prime factors of 2 in 72, so the correct answer is B.
This concludes our brief study of the “power of k” problems on the GMAT/EA. Join us next time for the final article in our series on exponents to learn how to handle problems with impossibly large numbers like 287459.
If you are in the middle of studying for the GMAT/EA and are looking for a private GMAT tutor, our elite tutors have all scored over 770 on the GMAT and have years of professional experience with tutoring. You can meet with us for a 30-minute complimentary consultation call.
Contributor: Elijah Mize (Apex GMAT Instructor)