GCD

This topic has expert replies
Master | Next Rank: 500 Posts
Posts: 424
Joined: Sun Dec 07, 2008 5:15 pm
Location: Sydney
Thanked: 12 times

GCD

by piyush_nitt » Fri May 08, 2009 5:29 am
What is GCD of positive integers m and n?
a. m is a prime number
b. 2n = 7m

IMO: C

User avatar
Site Admin
Posts: 2567
Joined: Thu Jan 01, 2009 10:05 am
Thanked: 712 times
Followed by:550 members
GMAT Score:770

by DanaJ » Fri May 08, 2009 10:18 am
1. so what? m could be 3 and n could be 6 (GCD is 3) or m could be 11 and n could be 5 (GCD is 1).

2. again, doesn't help much. For all I know, n is 7 and m is 2 (GCD is 1) or n is 14 and m is 4 (GCD is 2).

But if you put them all together: 7m = 2n means that 7m is an even number. Since 7 is not even, m must be even. But remember: m is a prime number. The only even prime number is 2, so m = 2. This means that n = 7 and since we have unique values for both m and n it's pretty easy to find their GCD.

Legendary Member
Posts: 1169
Joined: Sun Jul 06, 2008 2:34 am
Thanked: 25 times
Followed by:1 members

by aj5105 » Fri May 08, 2009 10:29 am
missed on this! duh!
DanaJ wrote:
2. again, doesn't help much. For all I know, n is 7 and m is 2 (GCD is 1) or n is 14 and m is 4 (GCD is 2).

User avatar
2009 Beat The GMAT Scholarship Winner
Posts: 182
Joined: Sat Mar 22, 2008 7:35 pm
Thanked: 3 times
Followed by:2 members
GMAT Score:700+

by gkumar » Thu Oct 22, 2009 3:26 pm
DanaJ wrote:1. so what? m could be 3 and n could be 6 (GCD is 3) or m could be 11 and n could be 5 (GCD is 1).

2. again, doesn't help much. For all I know, n is 7 and m is 2 (GCD is 1) or n is 14 and m is 4 (GCD is 2).

But if you put them all together: 7m = 2n means that 7m is an even number. Since 7 is not even, m must be even. But remember: m is a prime number. The only even prime number is 2, so m = 2. This means that n = 7 and since we have unique values for both m and n it's pretty easy to find their GCD.
Isn't the GCD 14 when n=7 and m=2? GCD of (14,14) = 14 since 2 and 7 are the common factors?

User avatar
Site Admin
Posts: 2567
Joined: Thu Jan 01, 2009 10:05 am
Thanked: 712 times
Followed by:550 members
GMAT Score:770

by DanaJ » Sat Oct 24, 2009 9:20 am
You are confusing greatest common divisor (GCD) with least common multiple (LCD).
Indeed, the LCD of 7 and 2 is 14. However, the GCD of 7 and 2 is 1.

GMAT/MBA Expert

User avatar
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 » Thu Jan 09, 2020 6:20 am
piyush_nitt wrote:What is GCD of positive integers m and n?
a. m is a prime number
b. 2n = 7m

IMO: C
Target question: What is the GCD of m and n?

Statement 1: m is a prime number
If m is a prime number, it has exactly 2 divisors (1 and m), so this tells us that the GCD of m and n must be either 1 or m.
Since we cannot answer the target question with certainty, statement 1 is NOT SUFFICIENT.

Statement 2: 2n = 7m
If 2n = 7m then we can rearrange the equation to get n = (7/2)m

IMPORTANT: Notice that if m were to equal an ODD number, then n would not be an integer. For example, if m = 3, then n = 21/2 (n is not an integer). Similarly, if m = 11, then n = 77/2 (n is not an integer). So, in order for n to be an INTEGER, m must be EVEN.

If m must be EVEN, there are several possible values for m and n. Consider these two cases:
case a: m = 2 and n = 7, in which case the GCD = 1
case b: m = 4 and n = 14, in which case the GCD=2
Since we cannot answer the target question with certainty, statement 2 is NOT SUFFICIENT.

Statements 1 & 2 combined
From statement 1, we know that m is prime, and from statement 2, we know that m is even.
Since 2 is the only even prime number, we can conclude that m must equal 2.
If m = 2, then n must equal 7, which means that the GCD must be 1.
Since we are able to answer the target question with certainty, statements 1 & 2 combined are sufficient, and the answer is C

Cheers,
Brent
Brent Hanneson - Creator of GMATPrepNow.com
Image