The greatest common factor of 16 and the positive integer n

GCF (n, 16) = 4
This means 4 is a factor of n but 8 and 16 are not. (If 8 were a factor of n too, the GCF would have been 8. Similarly for 16)

GCF (n, 45) = 3
This means 3 is a factor of n but 9 and 5 are not. Same logic as above.

210 = 2*3*5*7
n has 4 and 3 as factors and it doesn't have 5 as a factor.
so GCF of n and 210 could be 6 (if 7 is not a factor of n) or 42 (if 7 is a factor of n)

Answer (D)

Note: 3 is definitely not the GCF of n and 210 because they definitely have 3*2 in common. So GCF has to be at least 6.

EDIT.... My explanation was wrong :p [Correcting it]

Corrected Version:

Let's try the Prime Box Approach

Prime Box is simply a collection of all prime factors of a given number!

(1) Prime Box of 16 = |2, 2, 2, 2|
(2) Prime Box of 45 = |3, 3, 5|

(3) Prime Box of n = |2, 2, 3....|
(4) Prime Box of 210 = |2, 5, 3, 7|

From 3 and 4:
The GCF of n and 210 must be a multiple of 6.

So we can eliminate A, B and E!

From 2 and 3:
n is not a multiple of 5. If it were, the GCF of n and 45 would have been 15!
So we can eliminate C

The only remaining choice is 'D'

thanks Karishma ...my doubt is exactly the same thing but for 16 ..how come 42 is correct if n and 16 have a gcf of 4

That is because 210 has only one 2. Even though n has a 4 as factor, 210 does not. Therefore GCF of n and 210 does not have 4 as a factor. Does it make sense now?

so lets say if another choice was given as 6 then what could have been the ans or it would not be that close.

Then there would have been two correct options: 6 and 42. Either can be the GCF of n and 210 depending on what exactly n is.
GMAT never has 2 correct options and hence such a scenario is not possible. Only one of 6 and 42 would be in the answer choices.

The greatest common factor of 2^4=16 and n is 4 --> n is a multiple of 2^2=4 but not the higher powers of 2, for example 2^3=8 or 2^4=16, because if it were then the greatest common factor of 16 and n would be more than 4;

The greatest common factor of 3^2*5=45 and n is 3 --> n is a multiple of 3 but not the higher powers of 3 and not 5, because if it were then the greatest common factor of 3^2*5=45 and n would be more than 3;

So, n is a multiple of 2^2*3=12, not a multiple of higher powers of 2 or 3, and not a multiple of 5 (so n=12x where x could be any positive integer but 2, 3, or 5). Now, as 210=2*3*5*7 then the greatest common factor of n and 210 could be 6 or 6*7=42 (if 7 is a factor of n).

Answer: D.
_________________

You can do the prime boxes.

Prime box of 16: 2, 2, 2, 2
Prime box of 45: 3, 3, 5

Prime box of 210: 2, 5, 3, 7

So, n has at least two 2's and one 3, but n hasn't got any 5. Now, checking alternatives:
A) wrong, as n and 210 share at least one 2 and one 3.
B) wrong again, no 3 in 14.
C) wrong, as 30 has a 5
D) correct. 42 prime box is 2, 3, 7, so it meets all requirements.
E) wrong, 70 prime box has 2, 7 and 5

The greatest common factor of 16 and the positive integer n is 4, and the greatest common factor of n and 45 is 3. Which of the following could be the greatest common factor of n and 210?

Hi, let me try to explain in simpler way:

GCF = 4 = 2^2
16 = 2^4
that means prime box of n = 2^2 , ? ? ?

GCF = 3
45 = 3^2*5
that means prime box of n = 3^1, ? ? ?

Overall prime box of n = 2^2, 3^1, ???

Now, 210 = 3*7*5*2
from above we know the prime factor and powers of n (not complete ??)
therefore GCF = 3^1 * 2^1 * 7^1 (not 5 - we have seen above, but at least a 7 is possible)
Thus at least a GCF of 42 is possible here

Hope this helps

Simple explanation?

First, do a factor tree for each number.

You'll see that 5 can't be a factor of N (otherwise it would have been the highest factor between N and 45).

The highest factor that could theoretically exist between N and 210 is therefore all of the factors of 210 besides those we've ruled out. 210 is factored to 2 * 3 * 5 * 7. we've ruled out 5, so 2 * 3 * 7 = 42. Answer is D.

If the question asked "the highest factor that we KNOW exists" rather than "COULD" exist, the answer would be six since 2 and 3 are both factors of N, as well as of 210.

Hi Bunnel,

I have resolved this till n is a multiple of 2^2*3=12

why we are not considering 5 but we are considering 7.

Thanks

Notice that the GCF of 45 (a multiple of 5) and n is 3 (not a multiple of 5). This means that n itself cannot be a multiple of 5.

As for 7: we know for sure that 2 and 3 are factors of n and 5 is not a factor of n. We know nothing about its other primes, so any prime greater than 5 theoretically can be a factor of n.
_________________

16........ n .......................... n ....... 45

GCF = 4 ................................. GCF = 3

So n may be either 4 * 3 = 12 or a multiple of 12 to satisfy the GCF values given.

210 = 7 * 2 * 5 * 3

2, 3 & 5 are associated with 16 & 45. Including them in calculations will disturb the already provided GCF values

Only 7 stands out.

So 12 * 7 = 84

GCF of 84 & 210 = 42

Answer = D

n has to be a multiple of (2*2)*3 = 12
A common factor between 210= (2*3*5*7) and multiple of 12 is 2*3=6
So the G.C.F of n and 210 has to be a multiple of 6
The two choices that are multiples of 6 are 30 and 42.
Bur n is not a multiple of 5 .So 30 can be ruled out and the answer is 42.
_________________

This problem works best if you break it down into pieces with Venn diagrams.

16 and n have a GCF of 4 = 2^2. That means n has at least two 2's as factors.

45 and n share one factor: 3. That means n has at least one 3 and two 2's (3*2^2).

The next step is to break down 210 into 2*3*7*5. 5 is not a possible factor of n because it would've been a GCF with 45 and n. But 7 could be a common divisor because it's not expressly forbidden anywhere. So the GCF in this case is 2*3*7 = 42.

\(?\,\,\,:\,\,\,GCF\left( {n\,,2 \cdot 3 \cdot 5 \cdot 7} \right)\,\,\underline {{\rm{could}}\,\,{\rm{be}}}\)

\(n \ge 1\,\,\,{\mathop{\rm int}}\)

\(GCF\left( {{2^4},n} \right) = {2^2}\,\,\,\, \Rightarrow \,\,\,\,\,\left\{ \matrix{\\
{n \over {{2^2}}} = {\mathop{\rm int}} \hfill \cr \\
{n \over {{2^{\, \ge \,3}}}} \ne {\mathop{\rm int}} \hfill \cr} \right.\)

\(GCF\left( {{3^2} \cdot 5,n} \right) = 3\,\,\,\, \Rightarrow \,\,\,\,\,\left\{ \matrix{\\
{n \over 3} = {\mathop{\rm int}} \hfill \cr \\
{n \over {{3^{\, \ge \,2}}}} \ne {\mathop{\rm int}} \,\,\,\,\,;\,\,\,{n \over 5} \ne {\mathop{\rm int}} \,\, \hfill \cr} \right.\)

\(? = {2^1} \cdot {3^1} \cdot {7^{0\,{\rm{or}}\,1}}\,\,\,\,\,\mathop \Rightarrow \limits^{{\rm{alternatives}}\,!} \,\,\,\,42\,\,\,\,\,\,\left( D \right)\)


This solution follows the notations and rationale taught in the GMATH method.

Regards,
Fabio.
_________________

If the greatest common factor (GCF) of 16 and n is 4, n could be 4, 12, 20, 28, 36, etc. In other words, n is an odd multiple of 4.

Since the GCF of 45 and n is 3, and since 45 and 4 have no common factor other than 1, n must be a multiple of 3 x 4 = 12. However, since n is an odd multiple of 4, n actually has to be an odd multiple of 12 also.

If n = 12, we see that GCF(45, 12) = 3 and GCF(12, 210) = 6. However, 6 is not one of the choices.

If n = 36, we see that GCF(45, 36) = 9, but GCF(45, n) is supposed to be 3. So n can’t be 36.

If n = 60, we see that GCF(45, 60) = 15, but GCF(45, n) is supposed to be 3. So n can’t be 60.

If n = 84, we see that GCF(45, 84) = 3 and GCF(84, 210) = 42. We see that 42 is one of the choices.

Answer: D
_________________

Given: The greatest common factor of 16 and the positive integer n is 4, and the greatest common factor of n and 45 is 3.

Asked: Which of the following could be the greatest common factor of n and 210?

n = 4k ; where k is not a multiple of 2
45 = 3^2*5
n = 3m; where m is not a multiple of 3 or 5
210 = 2*3*5*7
n = 4*3*k ; where k is any prime other than 2,3,or 5

gcd (n,210) = 2*3 = 6 or 2*3*7 = 42

IMO D