The greatest common factor of 16 and the positive integer n

BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

This topic has expert replies

Post new topic Post Reply

Previous Topic Next Topic

BTGmoderatorLU: Moderator; Posts: 2505; Joined: Sun Oct 15, 2017 1:50 pm; Followed by:6 members

The greatest common factor of 16 and the positive integer n

by BTGmoderatorLU » Mon Oct 01, 2018 2:29 pm

Timer

00:00

Your Answer

Global Stats

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.

Quote

Source: Beat The GMAT — Problem Solving | Mon Oct 01, 2018 2:29 pm

fskilnik@GMATH: GMAT Instructor; Posts: 1449; Joined: Sat Oct 09, 2010 2:16 pm; Thanked: 59 times; Followed by:33 members

by fskilnik@GMATH » Mon Oct 01, 2018 3:19 pm

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.

Fabio Skilnik :: GMATH method creator ( Math for the GMAT)
English-speakers :: https://www.gmath.net
Portuguese-speakers :: https://www.gmath.com.br

Quote

GMAT/MBA Expert

Brent@GMATPrepNow: GMAT Instructor; Posts: 16207; Joined: Mon Dec 08, 2008 6:26 pm; Location: Vancouver, BC; Thanked: 5254 times; Followed by:1268 members; GMAT Score:770

by Brent@GMATPrepNow » Mon Oct 01, 2018 4:52 pm

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

Brent Hanneson - Creator of GMATPrepNow.com

Quote

GMATGuruNY: GMAT Instructor; Posts: 15539; Joined: Tue May 25, 2010 12:04 pm; Location: New York, NY; Thanked: 13060 times; Followed by:1906 members; GMAT Score:790

by GMATGuruNY » Mon Oct 01, 2018 5:29 pm

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.

Private tutor exclusively for the GMAT and GRE, with over 20 years of experience.
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.

As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.

For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3

Quote

GMAT/MBA Expert

Scott@TargetTestPrep: GMAT Instructor; Posts: 8086; Joined: Sat Apr 25, 2015 10:56 am; Location: Los Angeles, CA; Thanked: 43 times; Followed by:29 members

by Scott@TargetTestPrep » Wed Oct 03, 2018 4:40 pm

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

Scott Woodbury-Stewart
Founder and CEO
[email protected]