EgmatQuantExpert wrote:
Bunuel wrote:
What is the greatest value of x such that 8^x is a factor of 16! ?
A. 2
B. 3
C. 5
D. 6
E. 8
Since, we need to find the greatest value of x such that \(8^x\) is a factor of \(16!\), it is same as finding the highest power of 8 in \(16!\)
In any question where we need to find the highest power of a number which can divide a factorial (product of first n natural numbers) or in other words, is a factor of the given factorial, all we need to do is
1. Prime factorize the number whose highest power is to be found.
2. Find the highest power of each of the prime factors in the factorial
3. Calculate how many such numbers (whose highest power is to be found) can be created using the highest power of each of its prime factors.
Let's apply the above steps to solve this question and then we will look at a couple of questions where we can apply this learning.
We need to find the highest power of 8, so let's begin by doing
Step-1: Prime factorization of 8.\(8 = 2 * 2 * 2 = 2^3\)
Step-2: Find the highest power of each of the prime factors in the factorialSince 8 has only one prime factor 2, we need to find the highest power of 2 in 16!. Now how do we do so? There are 2 ways based on the same principle.
Method 1Keep dividing the factorial successively by 2 and keep adding the quotient till you don't have anything left to divide. Remember, successive division means dividing the quotient obtained at each step by the same divisor by which we start the division.So, let's do it quickly.
\(\frac {16}{2} = 8\)
\(\frac {8}{2} = 4\)
\(\frac {4}{2} = 2\)
\(\frac {2}{2} = 1\)
\(\frac {1}{2} = 0\)
As there is nothing left to divide, let's add the quotients to find the highest power of 2 in \(16!\)
Sum of quotients \(= 8+4+2+1+0 = 15\)
Method 2Divide 16 by consecutive powers of 2, till you get 0 as a quotient and add all quotients. This method is based on the same principle as Method 1.
So, we have highest power of 2 in 16! = \(\frac {16}{2} + \frac {16}{2^2} +\frac {16}{2^3}+\frac {16}{2^4} = 8+4+2+1 = 15\)
So, we can conclude that the highest power of 2 in \(16!\) is \(2^{15}\)
Step-3: Calculate how many such numbers can be created using the highest power of each of its prime factorsLet's try to figure how many 8's we can create using \(2^{15}\).
Since, \(8 = 2^3\), we can write \(2^{15}\) as \((2^{3})^5\).
Or, in simple terms \(2^{15} = 8^5\)
Hence, the greatest value of x such that \(8^x\) is a factor of 16! is 5. Hence, answer is choice C.
Let me post a couple of questions on similar lines where we can use the method discussed in this post to solve this type of questions very quickly.
Question 1: What is the greatest value of x such that \(15^x\) completely divides 300! ?
A. 20
B. 54
C. 74
D. 148
E. 222
Question 2: What is the greatest value of "a" such that \(45^a\) completely divides 300! ?
A. 8
B. 36
C. 74
D. 148
E. 222
Detailed solutions will be posted soon. Use the method highlighted in this post to solve the above questions. All the best.
To practise ten 700+ Level Number Properties Questions attempt the The E-GMAT Number Properties Knockout
Click here.Regards,
Piyush
e-GMATAlright so let's look at the detailed solution of the first question and the answer of the second question. Once you go through the above post and this solution, you should have a strong understanding of this approach. Let's use the
simple 3-step approach to solve questions similar to the above question.
Step 1. Prime factorize the number whose highest power is to be found.
Step 2. Find the highest power of each of the prime factors in the factorial
Step 3. Calculate how many such numbers (whose highest power is to be found) can be created using the highest power of each of its prime factors.
Let's apply the above steps to solve this question and then we will look at a couple of questions where we can apply this learning.
We need to find the highest power of 15, so let's begin by doing
Step-1: Prime factorization of 15.\(15 = 3*5 = 3^1*5^1\)
Step-2: Find the highest power of each of the prime factors in the factorialSince 15 has two prime factors 3 and 5, we need to find the highest power of 3 and 5 separately in 300!. Now how do we do so? There are 2 ways based on the same principle.
Note: The question can be solved by finding the highest power of 5 alone. However, we don't advocate using this shortcut until you're 100% confident about these questions. The reason is there are certain complicated factors that you need to keep in mind to use this shortcut without making errors and the advantage gained is not big enough to take that risk. Hence, let's find the highest powers of both the prime factors 3 and 5.
Method 1Keep dividing the factorial successively by 3 and keep adding the quotient till you don't have anything left to divide. Remember, successive division means dividing the quotient obtained at each step by the same divisor by which we start the division.So, let's do it quickly.
\(\frac {300}{3} = 100\)
\(\frac {100}{3} = 33\)
\(\frac {33}{3} = 11\)
\(\frac {11}{3} = 3\)
\(\frac {3}{3} = 1\)
\(\frac {1}{3} = 0\)
As there is nothing left to divide, let's add the quotients to find the highest power of 3 in \(300!\)
Sum of quotients \(= 100+33+11+3+1+0 = 148\)
Similarly, let's find the highest power of 5 in 300! by using the same method.
\(\frac {300}{5} = 60\)
\(\frac {60}{5} = 12\)
\(\frac {12}{5} = 2\)
\(\frac {2}{5} = 0\)
As there is nothing left to divide, let's add the quotients to find the highest power of 5 in \(300!\)
Sum of quotients \(= 60+12+2+0 = 74\)
Method 2Divide 300 by consecutive powers of 3, till you get 0 as a quotient and add all quotients. This method is based on the same principle as Method 1.
So, we have highest power of 3 in 300! = \(\frac {300}{3} + \frac {300}{3^2} +\frac {300}{3^3}+\frac {300}{3^4}+\frac {300}{3^5} = 100+33+11+3+1 = 148\)
So, we can conclude that the highest power of 3 in \(300!\) is \(3^{148}\)
Following a similar process to find the highest power of 5 in 300!, we get that the highest power is \(5^{74}\)
Step-3: Calculate how many such numbers can be created using the highest power of each of its prime factorsLet's try to figure how many 15's we can create using \(3^{148}\) and \(5^{74}\).
Since, \(15 = 3^1*5^1\), we can write \(300!\) as \(300!=3^{148}*5^{74}*k = (3*5)^{74} * 3^{74}*k =15^{74}*3^{74}*k\), where k is a positive integer
Or, in simple terms the highest power of 15 in 300 is \(15^{74}\).
Hence, answer is choice C.
If use the same approach to solve Q2, you will understand that \(45 = 3^2*5^1\).
The highest power of 3 in 300! is \(3^{148}\) and that of 5 is \(5^{74}\). Therefore, the highest power of 45 or \(3^2*5^1\) in 300! is 74. Hence, the answer is choice C.
Regards,
Piyush
e-GMAT