Current Student
Joined: 20 Aug 2019
Posts: 46
Location: Malaysia
Concentration: Strategy, General Management
GPA: 4
For any integer P greater than 1, P! denotes the product of all the in
[#permalink]
23 Jan 2020, 18:08
Given:
For any positive integer P, P! = P(P-1)(P-2) . . . * 3* 2 * 1
Since 48 is a positive integer, 48! = 48*47*46*45* . . . *3*2*1
To find: The greatest integer m for which 45m is a factor of 48!
Approach:
1. To determine the greatest possible value of m, we first need to understand when will 45m be a factor of 48!
45m = (32*5)m = 32m*5m
So, 45m is a factor of 48! only if:
32m is a factor of 48! AND
5m is a factor of 48!
We need to find the greatest value of m that satisfies this constraint
2. We’ll find the greatest value of m for which 32m is a factor of 48! Let this value be x
To find x, we’ll calculate the power of 3 in the prime-factorized expression of 48!
3. Next, we’ll find the greatest value of m for which 5m is a factor of 48! Let this value be y
To find y, we’ll calculate the power of 5 in the prime-factorized expression of 48!
4. The greatest value of m for which 32m and 5m are both factors of 48! will be equal to the lesser value between x and y
Working Out:
Finding the value of x
We first need to calculate the power of 3 in the prime-factorized expression for 48!
As inferred above, 48! = 48*47*46*45* . . . *3*2*1
The multiples of 3 in the above product are: {3, 6, 9, 12, 15, 18, 21, 24 . . . 48}
Upon counting, we see that there are 16 multiples of 3
Note: To ease the counting, here’s a simple trick: 3 = 3*1 and 48 = 3*16. This means, starting from 3 till 48, inclusive, there are 16 multiples of 3
So, each of these multiples of 3 contributes at least one 3 to the prime-factorized form of 48!
So, the number of 3s we’ve counted so far = 16
Now, note that some multiples of 3 in the list above are also multiples of 9 (= 32). These multiples therefore contain not one but two 3s. The number 16 calculated above considers only one 3 contributed by each multiple. So, we need to know how many multiples of 9 are there between 1 and 48 to know how many additional 3s they contribute.
There are 5 multiples of 9 between 1 and 48.
So, these 5 multiples contribute at least one more 3 each to the prime-factorized form of 48! (in addition to the one 3 already counted when counting the multiples of 3 in the above point)
So, the number of 3’s counted so far = 16 + 5 = 21
Note that one multiple of 9 in the list above is also a multiple of 27 = 33. This is the number 27 itself. So, this number contributes one more 3 to the prime-factorized form of 48!
So, the total number of 3s in the prime-factorized form of 48! = 21 + 1 = 22
Therefore, the power of 3 in the prime-factorized form of 48! Is 22
Hence, the maximum power of 3 which can divide 48! completely is 322
So, for 32m to divide 48!
The maximum value of 2m = 22
The maximum value of m = 11
That is, x = 11
Important Takeaway:
We can summarize the process we used above to find the power of 3 in 48!, in the following formula:
(Power of 3 in 48!)
= (Number of multiples of 3 in 48!) + (Number of multiples of 32 in 48!) + (Number of multiples of 33 in 48!)
Good so far?
Now comes the interesting point:
We can follow this same process to find the power of any prime number X in P! where P is any positive integer
The general formula to summarize the above process will be:
(Power of prime-factor X in P!)
= (Number of multiples of X in P!) + (Number of multiples of X2 in P!) + (Number of multiples of X3 in P!) + ...
Finding the value of y
We first need to find the power of 5 in the prime-factorized expression for 48! This time, we’ll use the formula to find this power.
Once again, we’ll start by writing 48! = 48*47*46*45* . . . *3*2*1
The multiples of 5 in the above product are: {5, 10, 15 . . . 45}
Upon counting, we see that there are 9 multiples of 5
There is only 1 multiple of 52 (that is, 25) in 48!. This multiple is number 25 itself.
So, the power of 5 in the prime-factorized form of 48! = 9 + 1 = 10
Therefore, the maximum power of 5 which can divide 48! completely is 510
So, for 5m to divide 48!
The maximum value of m = 10
That is, y = 10
Finding the greatest possible value of m
We’ve determined that x = 11 and y = 10
The lesser value out of 10 and 11 is 10
So, the greatest value of m for which 45m is a factor of 48! Is 10 (because if m = 11 then 32m = 322 will be a factor of 48! But 5m = 511 will not be a factor of 48!)
Looking at the answer choices, we see that the correct answer is Option D