Bunuel wrote:
What is the smallest positive integer n for which n!/9^9 is an integer?
A. 36
B. 39
C. 54
D. 78
E. 81
Official solution from
Veritas Prep.
This is a number theory question – note the term “positive integer” and the fact that the question is essentially asking about the divisibility of \(n!\). As such, we will begin by prime factoring \(9^9\) as \((3^2)^{9}=3^{18}\). The real question is how far we have to go to find eighteen copies of 3.
The cop-out answer would be to simply take \(n=18∗3=54\); \(54!\) definitely contains at least eighteen factors of 3, since it contains \(3∗1, 3∗2, 3∗3, …, 3∗18\). However, \(54!\) actually contains far more than just the eighteen 3s, since several factors contain “bonus” 3s. For instance, \(54!\) contains 9, which is \(3^2\), and 27, which is \(3^3\), and even 54 itself, which is \(2∗3^3\). The correct answer must be less than 54.
At this point we could calculate the exact number of 3s in \(54!\) (it has twenty-six of them, as it turns out) and adjust from there, but it might be simpler to just try answers A and B, since one or the other must be correct.
\(36!\) contains twelve multiples of 3 (\(3∗1\) through \(3∗12\)), but it also contains four multiples of 9 (\(9∗1\) through \(9∗4\)), each of which provides an additional factor of 3, since \(9=3^2\). And \(36!\) Even contains one multiple of \(3^3=27\), which provides an “additional” additional 3. Taken together, \(36!\) contains \(12+4+1=17\) factors of 3, just short of our goal.
We can see at this point that \(39!\) provides exactly one more 3 than does \(36!\), since \(39!=39∗38∗37∗36!\).
Therefore, \(39!\) contains exactly 18 factors of 3, and answer B is correct.
_________________
"Be challenged at EVERY MOMENT."“Strength doesn’t come from what you can do. It comes from overcoming the things you once thought you couldn’t.”"Each stage of the journey is crucial to attaining new heights of knowledge."Rules for posting in verbal forum | Please DO NOT post short answer in your post!
Advanced Search : https://gmatclub.com/forum/advanced-search/