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?

3

14

30

42

70

Can anyone explain how to solve this Question.

I would start by taking the prime factorization of 16 --> 2^4

If the GCF(16, n) = 4 (where n is a positive integer), then we know that there are at least two 2's in n's prime box.

If the GCF(45,n) = 3 then we know two additional pieces of information.

1) Given that the prime factorization of 45 is 3^2 * 5, then we know that 5 *isn't* in n's prime box

2) At least one 3 *is* in n's prime box

So now we have at least two 2's and at least one 3 in n's prime box.

The question is asking for possible values for GCF(n, 210).

210's prime factorization = 7 * 3 * 2 * 5
n's (partial) prime factorization = 2 * 2 * 3...

Since 210 and n at least share one 2 and one 3, we can eliminate A as a possible choice. C and E can be eliminated because we know that 5 is not in n's prime box. B can also be eliminated because we already know that 210 and n share one 2 and one 3 and the prime factorization of 14 (2 * 7) does not contain a 3.

That leaves D as the only possible answer.

Prime factorization of 42 = 2 * 3 * 7

Nice job aramak; I would only point out that we know that n has EXACTLY two 2s and EXACTLY one 3. If it had three or more 2s its greatest common factor with 16 would be 8; if it had two or more 3s its greatest common factor with 45 would be 9. You are absolutely correct that n cannot have a 5 as a factor.

_________________
Jamie Nelson
ManhattanGMAT Instructor

The question states that the GCF of n and 16 is 4. The possible numbers for n to satisfy this are 4, 8 and 12. However the next line states that the greatest common factor for n and 45 is 3.

Considering the first two statements, I concluded that n is 12. I realize that the answer is wrong but I am curious to know what would be the correct value of 'n' that would satisfy the criteria given in the question.

This is where you made the wrong conclusion. Those are numbers which [almost] satisfy the statement but not the only ones. You must start with 4 (as you have done) but after that you can add any prime factor other than 2 to n [for that reason, your example of 8 would be incorrect since 8 would be the GCF]. As pointed out earlier, if n contains one more 2, 8 would then be the GCF.

Some examples: The GCF of 16 and the following are 4
20 = 4 * 5
28 = 4 * 7
44 = 4 * 11
4620 = 4 * 3 * 5 * 7 * 11
and so forth.

Thanks..makes sense. However, what would be the number 'n' that satisfies the criteria given in this question. How do we find that?
Thanks a lot.

As per the answer and the information given in the question,

GCF of n and 210 is 42
GCF of n and 16 is 4
GCF of n and 45 is 3.

If this is true, what is the value of n? I am unable to find any value of n that satisfies all the above criteria.

There are infinite values. 84 or many multiples of 84 could satisfy all the conditions.

Well, thanks Mithun. 84 was the answer I was looking for and i missed it. However it is wrong to state that there can be infinite values and definitely multiples of 84 would not satisfy the conditions. For examples, 168 would be divisible by 8 and so definitely 4 would not be a GCF of 168 and 16.

84 would come out to be the correct answer if we do the prime factorization for all the numbers and get the HCF.

84 = 2*2*3*7
16 = 2*2*2*2
210 = 7*3*2*5
45 = 3*3*5

As per the answer and the information given in the question,

GCF of n and 210 is 42
GCF of n and 16 is 4
GCF of n and 45 is 3.

If this is true, what is the value of n? I am unable to find any value of n that satisfies all the above criteria.[/quote]

There are infinite values. 84 or any multiple of 84 could satisfy all the conditions.[/quote]

There are infinite solutions. I meant to say "many" instead of "any" in my post. I corrected it.

You can multiple 84 with primes that are not common to 210, 16, or 45. For example, 11, 17, 19 etc... There are infinite solutions.

Hi Mithun,

Thanks for the answer on 84 again and yes now I understand your point with many other solutions. Thanks again.

Thanks everyone!

_________________
Jamie Nelson
ManhattanGMAT Instructor