Problem Solving

I was hoping to get some clarification on Problem 169 from Quantitative Review 2nd Ed:

Q: If n is a positive integer and n^2 is divisible by 72, then the largest positive integer that must divide n is:
A 6, B 12, C 24, D 36, E 48

n^2 is divisible by 72, but it must also be greater than 72. If n is an integer, then n^2 must be a perfect square. The factorization of 72 is (8)(9), so if it is multiplied by 2, it will be (2)(8)(9) = (16)(9) = 144, a perfect square. So n^2 must be at least 144 or a multiple of 144, which means that n must be 12 or a multiple of 12.

I know that Quantitative Review also has 12 as the answer, but I had a question: Since n must be 12 or a multiple of 12, why is it that 48 isn't a solution since its a multiple of 12 and 48 divides 48 and is also the greatest number amongst the solutions, especially because the question does not state 'largest integer other than n that divides n'? What is the concept that I am not getting?

Please help.

72's prime factorization is

(2^3)(3^2)

A square's prime factors must be to even powers, for example, 4=2^2, 16=2^4, 81=3^4. So if n^2 is divisible by 72, then n^2 is at least 72's prime factors to even integer powers, the square of those factors. 72's prime factors are;

(2^3)(3^2), thus then N squared must be at least, (2^4)(3^2).

(2^4)(3^2)=144

Sqrt(144)=12, so the largest postive integer that n must be divisible by is 12.

This also speaks to the fact that the least common factors of two numbers is also the greatest possible distance between two numbers.

For a more thorough discussion on the topic please refer to Manhattan GMAT's Number Properties strategy guide, Chapter 10 Divisibility & Primes Advanced Strategy.

Hope that helps.

Thanks,

Jared

dghosh2602 wrote:I was hoping to get some clarification on Problem 169 from Quantitative Review 2nd Ed:

Q: If n is a positive integer and n^2 is divisible by 72, then the largest positive integer that must divide n is:
A 6, B 12, C 24, D 36, E 48

n^2 is divisible by 72, but it must also be greater than 72. If n is an integer, then n^2 must be a perfect square. The factorization of 72 is (8)(9), so if it is multiplied by 2, it will be (2)(8)(9) = (16)(9) = 144, a perfect square. So n^2 must be at least 144 or a multiple of 144, which means that n must be 12 or a multiple of 12.

I know that Quantitative Review also has 12 as the answer, but I had a question: Since n must be 12 or a multiple of 12, why is it that 48 isn't a solution since its a multiple of 12 and 48 divides 48 and is also the greatest number amongst the solutions, especially because the question does not state 'largest integer other than n that divides n'? What is the concept that I am not getting?

Please help.

If n is a positive integer and n^2 is divisible by 72, then the largest positive integer that must divide n does not exist, because for that to exist we need to look for the greatest square multiple of 72, which again doesn't exist. I am not convinced with the wordings here.

Since N^2 is multiple of 72 and N is an integer,
N^2 should be of the form[2^3*3^2*2]*k; where k is a positive integer with even power.

Let's for the argument sake say the maximum value that k may take is 4 (2^2).
so N^2 = 576 and N = 24. So let's say (wrongly) that the largest positive integer that must divide N is 24.

But , as per the rule above in bold, we may very well have k = 1^2, and hence N^2 = 144, so N = 12.
Now 24 can not divide 12. Since, we need to find the largest possible integer that MUST (for any N) divide N.
And you may observe how this search of 'largest' positive integer actually translates to a search of 'smallest' positive integer.

n^2 = 72 K as provided
so for (2*2)*(3*3) *2 * K to be a perfect square of n , K = 2 * {square of some number}

so n^2 = 72 K = (2*2)*(3*3) *2 * 2 * {square of some number } - lets call square of some number = a^2
n=square root of [ (2*2)*(3*3) *2 * 2 * {a^2}
n = 2 * 3 * 2 * a
n=12a
So the largest number that always divides n is 12

debmalya_dutta wrote:n^2 = 72 K as provided
so for (2*2)*(3*3) *2 * K to be a perfect square of n , K = 2 * {square of some number}

so n^2 = 72 K = (2*2)*(3*3) *2 * 2 * {square of some number } - lets call square of some number = a^2
n=square root of [ (2*2)*(3*3) *2 * 2 * {a^2}
n = 2 * 3 * 2 * a
n=12a
So the largest number that always divides n is 12

how come?