GCD

Expert replies

knight247: Legendary Member; Posts: 504; Joined: Tue Apr 19, 2011 1:40 pmFollowed by: 11 members; Thanked: 114 times

by knight247 » Tue Feb 14, 2012 1:14 am

m=4n+9, where n is a positive integer. What is the GCD of m and n?
(1)m=9s, where s is a positive integer
(2)n=4t, where t is a positive integer

OA is A

Like this post

Source: Beat The GMAT — Problem Solving | Tue Feb 14, 2012 1:14 am

sanju09: GMAT Instructor; Posts: 3650; Joined: Wed Jan 21, 2009 4:27 amFollowed by: 80 members; Location: India; Thanked: 267 times; GMAT Score:760

by sanju09 » Tue Feb 14, 2012 5:39 am

knight247 wrote:m=4n+9, where n is a positive integer. What is the GCD of m and n?
(1)m=9s, where s is a positive integer
(2)n=4t, where t is a positive integer

OA is A

What we know is that m is an odd positive integer.

I. If m = 9s, where s is a positive integer, then n is also a multiple of 9 otherwise 9s cannot be equal to 4 n + 9, thus we can trust that n = Â¼ (9s - 9) or n = (9/4) (s - 1). So we can further realize that s - 1 is divisible by 4 or at minimum, s is odd and it may or may not be a multiple of 9 but it surely is not a multiple of 4. Now, to find the GCD of m and n all we need to decide is what is the GCD of s and Â¼ (s - 1) where s could be 5, 9, 13, etceteras or hence Â¼ (s - 1) could be 1, 2, 3, etceteras respectively. See, all such pairs (5, 1), (9, 2), (13, 1) etceteras contain two co primes with GCD 1. Hence, the GCD of 9s and (9/4) (s - 1) is 9, or the GCD of m and n is 9. To believe this, we can have another point of view, let's take Â¼ (s - 1) = k, so that s = 4 k + 1 and k and 4 k + 1 cannot have a prime in common.

Remaining of the post tomorrow as I am in hurry...

The mind is everything. What you think you become. -Lord Buddha

Sanjeev K Saxena
Quantitative Instructor
The Princeton Review - Manya Abroad
Lucknow-226001

www.manyagroup.com

Like this post

GMAT/MBA Expert

Anurag@Gurome: GMAT Instructor; Posts: 3835; Joined: Fri Apr 02, 2010 10:00 pmFollowed by: 523 members; Location: Milpitas, CA; Thanked: 1854 times; GMAT Score:770

by Anurag@Gurome » Tue Feb 14, 2012 5:43 am

knight247 wrote:m=4n+9, where n is a positive integer. What is the GCD of m and n?
(1)m=9s, where s is a positive integer
(2)n=4t, where t is a positive integer

OA is A

(1) m = 9s implies m is a multiple of 9.
But m = 4n + 9 implies 4n + 9 should also be a multiple of 9. For 4n + 9 to be a multiple of 9, 4n should also be a multiple of 9 and hence n should also be a multiple of 9. So, GCD of m and n is 9; SUFFICIENT.

(2) n = 4t
If t = 9, then n = 4 * 9, and m = 4n + 9 implies GCD of m and n is 9.
If t = 1, then n = 4 * 1 and m = 4n + 9 implies GCD of m and n is 1.
No unique answer; NOT sufficient.

The correct answer is A.

Anurag Mairal, Ph.D., MBA
GMAT Expert, Admissions and Career Guidance
Gurome, Inc.
1-800-566-4043 (USA)

Join Our Facebook Groups
GMAT with Gurome
https://www.facebook.com/groups/272466352793633/
Admissions with Gurome
https://www.facebook.com/groups/461459690536574/
Career Advising with Gurome
https://www.facebook.com/groups/360435787349781/

Like this post

Post new topic Post Reply

• Page 1 of 1

GMAT Course Reviews

559 reviews

1168 reviews

431 reviews

359 reviews

147 reviews

5/5

5 Star (560 Reviews)

"Target Test Prep is the closest to the official version of the GMAT exam, about 99% accuracy in terms of the quality and quantity of information. The course has excellently created singular sets of focused lessons and tests for every possible topic that one could come across in the official GMAT exam."

"The TTP course maximizes the efficiency of the time you spend studying. It will take time and effort but I could almost guarantee that if you complete the course exactly as it is laid out you will get an amazing score. They also have a very responsive team willing to help with any questions you might have."

"TTP has two things that I think no other test prep company offers: A teaching approach that reinforces understanding and an attitude that will give you the mental preparedness needed to succeed on the test. TTP gives you a deep understanding of the concept you need to know while teaching you how to think."

Write a Review