GMAT Practice Question: If n=9!-6^{4}, which of the following is the greatest integer k such that 3^{k}...
Question
If n=9!-6^{4}, which of the following is the greatest integer k such that 3^{k} is a factor of n ?
- 1
- 3
- 4
- 6
- 8
Topics: factorials, divisibility, number theory, exponents, factoring
Solution
Step 1
We first find how many times 3 appears in 9! by counting its factors in the numbers 3, 6, and 9.
9! = 1\times2\times3\times4\times5\times6\times7\times8\times9 = 3^1\times(2\times3^1)\times3^2\times\text{(other factors not divisible by }3) = 3^4\times\text{(integer not divisible by }3)
Step 2
We then break down 6^4 into its prime factors.
6^4 = (2\times3)^4 = 2^4\times3^4
Step 3
We now factor out the common 3^4 from both terms in the expression for n.
n = 9! - 6^4 = 3^4\times(\frac{9!}{3^4} - \frac{6^4}{3^4})
Step 4
We simplify the first fraction by canceling four factors of 3 from 9!.
9! = 1\times2\times3\times4\times5\times6\times7\times8\times(3\times3) = 1\times2\times\cancel{3}\times4\times5\times(2\times\cancel{3})\times7\times8\times(\cancel{3}\times\cancel{3}) \frac{9!}{3^4} = 1\times2\times4\times5\times2\times7\times8 = 4480
Step 5
We simplify the second fraction by dividing out all factors of 3 from 6^4.
\frac{6^4}{3^4} = \frac{(2\times3)^4}{3^4} = 2^4 = 16
Step 6
We then subtract to find the integer inside the parentheses.
4480 - 16 = 4464
Step 7
We next find how many times 3 divides into 4464 by testing divisibility by 9 and then by 3.
4 + 4 + 6 + 4 = 18 \text{Since }18\text{ is divisible by }9,\;4464\text{ is divisible by }9 \frac{4464}{9} = 496 4 + 9 + 6 = 19 \text{Since }19\text{ is not divisible by }3,\;496\text{ is not divisible by }3
Step 8
We now add the exponent of 3 from the remainder to the exponent we factored out to get the total exponent.
n = 3^4\times(3^2\times496) = 3^{4+2}\times496 = 3^6\times496
Answer
6
