The greatest common factor of 16 and the positive integer n

Question

Source: Manhattan Prep 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? A. 3 B. 14 C. 30 D. 42 E. 70 The OA is D.

fskilnik@GMATH · Answer

BTGmoderatorLU wrote:Source: Manhattan Prep 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? A. 3 B. 14 C. 30 D. 42 E. 70 $$?\,\,\,:\,\,\,GCF\left( {n\,,2 \cdot 3 \cdot 5 \cdot 7} \right)\,\,\underline {{\text{could}}\,\,{\text{be}}} $$ $$n \geqslant 1\,\,\,\operatorname{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.

Brent@GMATPrepNow · Answer

BTGmoderatorLU wrote:Source: Manhattan Prep 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? A. 3 B. 14 C. 30 D. 42 E. 70 The OA is D. Now, we can use ELIMINATION to find the correct answer. Goal: Find GCF of 210 and n. 210 = (2)(3)(5)(7) The greatest common factor of 16 and the positive integer n is 4 16 = (2)(2)(2)(2) 4 = (2)(2) So, we know for certain that the PRIME FACTORIZATION of n has TWO 2's (and no more than TWO) In other words, n = (2)(2)(?)(?)... Since 210 = (2)(3)(5)(7), we can see that 210 and n both share ONE 2. So, the GCF of 210 and n will be divisible by 2. We can ELIMINATE A, since 3 is not divisible by 2. The greatest common factor of n and 45 is 3 45 = (3)(3)(5) 3 = 3 So, we know for certain that the PRIME FACTORIZATION of n has ONE 3 (and no more than ONE) In other words, n = (3)(?)(?)(?)... Since 210 = (2)(3)(5)(7), we can see that 210 and n both share ONE 3. So, the GCF of 210 and n will be divisible by 3. We can ELIMINATE B and E, since they are not divisible by 3. This leaves C (30) and D (42). Finally, notice that, since the GCF of n and 45 is 3, we can be certain that n does NOT have a 5 in its prime factorization. Otherwise, the GCF of n and 45 would be 15. This means that n is NOT divisible by 5, which also means the GCF of 210 and n will NOT be divisible by 5 So we can ELIMINATE C. This leaves us with D, the correct answer. Cheers, Brent

GMATGuruNY · Answer

BTGmoderatorLU wrote:Source: Manhattan Prep 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? A. 3 B. 14 C. 30 D. 42 E. 70 The greatest common factor of 16 and the positive integer n is 4, and the greatest common factor of n and 45 is 3. Draw a VENN DIGRAM showing where the prime factors of n, 16 and 45 overlap: The diagram implies the following: Since n and 16 have only two 2's in common, the prime-factorization of n includes exactly two 2's. Since n and 45 have only a 3 in common, the prime-factorization of n includes exactly one 3 and no 5's. Thus: n = 2*2*3*k, where k is not a multiple of 2, 3, or 5. Since n is not a multiple of 5, the GCF of n and 210 cannot be a multiple of 5. Eliminate C and E. Since n = 2*2*3*k and 210 = 2*3*5*7, the GCF of n and 210 must be a multiple of 6, as indicated by the factors in red. Eliminate A and B. The correct answer is D.

Scott@TargetTestPrep · Answer

BTGmoderatorLU wrote:Source: Manhattan Prep 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? A. 3 B. 14 C. 30 D. 42 E. 70 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

Choose how you want to prepare

Get Ready for GMAT Test Day Faster with Live Online Classes

Target Test Prep EA OnDemand

Target Test Prep GMAT OnDemand

The greatest common factor of 16 and the positive integer n

GMAT/MBA Expert

GMAT/MBA Expert

Chicago Booth

GMAT Course Reviews

Admissions Consulting Reviews

FREE GMAT PREP RESOURCES

GMAT PREP DEAL TRACKER