GRE problem involving LCD, prime factorization, and sets.

Question

I think this problem was a bit tricky and I'm trying to better think through this. Here is the problem:

Let S be the set of all positive integers n such that $n^2$ is a multiple of both 24 and 108. Which of the following integers are divisors of every integer n in S?

• So I'm trying to first figure the LCM of 24 and 108
• 24's prime factorization is $2^33^1$ and 108's prime factorization is $2^23^3$. So the LCM is $2^3 3^3$ which is 27 * 8 = 216.
• We know that $n^2$ is a multiple of 216 or $2^3 3^3$ but this does not mean that every multiple of 216 is a possible value of $n^2$ because some multiples of 216 may not be squares of a number.

Where do I go from here?

Answer 1

Whenever you see anything about divisibility, you want to take the integers down to their prime factors in these steps.

1) First, I need to find the smallest multiple of both 24 and 108 so that I can find the smallest value of n2, and thus find the smallest value of n. As mentioned, I need to take them to the primes in order to do it. The prime factors of 24 are 2 x 2 x 2 x 3. This means that any multiple of 24 must have at least three twos and one three to be a multiple of 24. The prime factors of 108 are 2 x 2 x 3 x 3 x 3. This means that every multiple of 108 must have at least two twos and three threes to be a multiple of 108. Since some of the two and threes overlap, we can thus say that every multiple of BOTH 24 and 108 must have at least three twos (the minimum need to make 24, with plenty for 108) and at least three threes (the minimum to make 108 with plenty for 24). Thus, the smallest number that is a multiple of 24 and 108 is 2 x 2 x 2 x 3 x 3 x 3

2) Next, I need to find the smallest possible value of n2 so that I can find the smallest value of n. So we've got this magic number 2 x 2 x 2 x 3 x 3 x3, but while that's the smallest multiple of 24 and 108, it's not the smallest possible value of n2 because n2 is clearly a perfect square, and 2 x 2 x 2 x 3 x 3 x3 is not, because I can't just cut half of factors out and be left with an integer. I want the smallest perfect square, so I add a 2 and a 3 and get 2 x 2 x 2 x 2 x 3 x 3 x 3 x 3. This is acceptable because it is still a multiple of both 24 and 108 (which I know, because it contains the minimum required prime factors to make 24 and 108). This is the smallest value of n2.

3) I need to find the smallest possible value of n. To find the smallest possible n, I take the square root of that. That means I chop out half of the twos and half of the threes. So I have 2 x 2 x 3 x 3. This is the smallest value of n, and it is 36.

4) I compare n with the answer choices. So whatever answers divide evenly into 36 are correct.

Hope this helps! Goodluck.

Answer 2

The minimum element of S, call it $m$, is going to be the GCD of all its elements.

We have $24 = 2^3 * 3$, so $2^2$ and $3$ must be factors of $m$ for $m^2$ be a multiple of $24$.

Similarly, $108 = 2^2 * 3^3$, so $2$ and $3^2$ must divide $m$.

Knowing that, the minimum $m$ we can obtain so that $2^2, 3, 2$ and $3^2$ divide $m$ is $m = 2^2 * 3^2 = gcd(${$x|x\in S$}$)$.

Answer 3

If $n^2$ is a multiple of $2^33^3$ means $n^2$ is a multiple of $2^43^4$ as the prime factors of a square must be to even powers[*]. So $n$ is a multiple of $2^23^2 = 36$. So S is the multiples of 36; any multiples of 36. e.g. 72 is in S as $72^2$ is a multiple of $24$ ($72^2 = 3*24*72$) and of $108$ ($72^2 = 9^2*8^2 = 9*12*3*4*16 = 108 *3*4*16$).

We can verify this:

If $n = m*36$ => then $n^2 = 1296*m^2$ and both 24 and 108 divide 1296.

If $n \ne m*36$ then either 4 does not divide n, or 9 does not divide n. If 4 does not divide n, then 16 does not divide $n^2$. But $16|216 = \text {lcm}(24,108)$ so $\text {lcm}(24,108)$ does not divide $n^2$ and it isn't can't be that both 24 and 108 divide $n^2$.

Similarly if 9 does not divide n, then 81 does not divide $n^2$. But $81|216$ so 216 does not divide $n^2$ so it can not be that 24 and 108 both divide $n^2$.

So S = {multiples of 36}.

[*] Let $n = \prod p_i^{n_k}$ be the prime factorization of n. Then $n^2 =\prod p_i^{2n_k}$ is the prime factorization of $n^2$. Any square has only even powers in its prime factorization.

So if $2^32^3 | n^2$ then $n^3 = 2^{2k_1}3^{2k_2}\prod p_i^{2k_i}$ and $2k_1 \ge 3$ and $2k_2 \ge 3$ but $2k_1$ and $2k_2$ are even so $2k_1 \ge 4$ and $2k_2 \ge 4$. So $2^43^4 | n^2$

Answer 4

I understand why 36 is the lowest value in S. The part I am not able to understand is why all the bigger values in S has to be all the integer multiples of 36? Can some one explain that part to me please ?