# 1x2x3x...x99x100=(12^n)MIf 1x2x3x...x99x100=(12^n)M, where M is a natural number and n is the largest natural number possible while still keeping the equation true, then M ____.(A) is divisible by...

1x2x3x...x99x100=(12^n)M

If 1x2x3x...x99x100=(12^n)M, where M is a natural number and n is the largest natural number possible while still keeping the equation true, then M ____.
(A) is divisible by 2, but not by 3
(B) is divisible by 3, but not by 2
(C) is divisible by 4, but not by 3
(D) is not divisible by 3 or 2

Posted on

We want to find the largest integer `n` such that

`1*2*3*...*99*100=(12^n)M=(2^2*3)^nM=2^(2n)*3^nM` where `M` is an integer. We count the number of twos that occur in the LHS. There are `50` multiples of two (2,4,6,...,100). But each multiple of four has two twos, so we have to count (4,8,12,...,100) again, giving us `25` more factors of two. Each of the `12` multiples of eight (8,16,...,96) will give another factor of two, and the `6` multiples of 16, the `3` multiples of 32, and finally the `1` multiple of 64.

If we add all of these together, we see that the left side is divisible by 2 to the `50+25+12+6+3+1=97th` power, but no higher.

If we do something similar and count the factors of 3 on the LHS, we see that there are `33` multiples of 3, `11` more from the multiples of 9, `3` from the multiples of 27, and `1` from the lone multiple of 81. Thus there are `33+11+3+1=48` factors of 3 on the LHS.

So `n=48` is what we want, and we see that the RHS must be of the form

`2^(96)*3^(48)M.` Now the RHS already has all the factors of 3 accounted for in `3^(48)` , so `M` can't be divisible by 3. But here 2 is only raised to the 96th power and there should be 97 factors of two. Thus `M` must be divisible by 2 (but not 4, because that would make 98 factors of two on the right hand side while the left only has 97).

`M` is divisible by 2, but not by 3. Choice A is correct.