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

Redeem

What is the greatest common divisor ?

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Source: — Data Sufficiency |
User avatar
Master | Next Rank: 500 Posts
Posts: 170
Joined: Tue May 26, 2009 12:00 pm
Thanked: 5 times

by yogami » Sun Jul 26, 2009 12:37 pm
From (1) if we substitute values we get
since x = 12u, y = 3(u - 1)/2
This means that 2 can be a factor of u - 1 only when u is an odd integer but that is not guaranteed hence this is insuff

From (2) y = 12z implies x = 12(8*z + 1) and you can clearly see 12 as a common factor
So suff
200 or 800. It don't matter no more.
Top
Legendary Member
Posts: 1799
Joined: Wed Dec 24, 2008 3:03 am
Thanked: 36 times
Followed by:2 members

by goelmohit2002 » Sun Jul 26, 2009 1:08 pm
yogami wrote: From (2) y = 12z implies x = 12(8*z + 1) and you can clearly see 12 as a common factor
So suff
Thanks yogami.

But 12 is a common factor...but the question is asking about greatest common factor...

why 12 is the greatest ? Why not 24, 36, 48, 60....

How to prove that 12 or any of the above numbers is the greatest common factor....
Top
Legendary Member
Posts: 1799
Joined: Wed Dec 24, 2008 3:03 am
Thanked: 36 times
Followed by:2 members

by goelmohit2002 » Mon Jul 27, 2009 8:54 am
Can someone please help to solve this question ?
Top
Master | Next Rank: 500 Posts
Posts: 186
Joined: Sat Sep 02, 2006 7:50 pm
Thanked: 10 times
Followed by:1 members

by ogbeni » Mon Jul 27, 2009 10:16 am
@goelmohit2002

I'm with you. How do you know for certain that 12 is the GCD/GCF

I know from my Manhattan GMAT Number Properties Guide that the GCF of X and Y cannot be greater than X-Y.

Consider X(96Z+12) - Y(12Z) = 84Z+12. So the GCF/GCD of X and Y cannot be greater than 84Z+12 but we don't know what Z is and it could be 24, 48, 36......
Top
Legendary Member
Posts: 1799
Joined: Wed Dec 24, 2008 3:03 am
Thanked: 36 times
Followed by:2 members

by goelmohit2002 » Mon Jul 27, 2009 10:32 am
ogbeni wrote: I know from my Manhattan GMAT Number Properties Guide that the GCF of X and Y cannot be greater than X-Y.
Thanks ogbeni.

The above is something new to me....I was of the opinion that gcd/gcf of X and Y is less than or equal to the lower of (X,Y).....

e.g. 2,6....the gcf is 2....

Can you please give one example where gcf is greater then lower of two numbers ? for e.g. above X -Y comes to be 4.....
Top

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 2623
Joined: Mon Jun 02, 2008 3:17 am
Location: Montreal
Thanked: 1090 times
Followed by:355 members
GMAT Score:780

by Ian Stewart » Mon Jul 27, 2009 11:53 am
The GCD of two numbers can't be larger than either of the numbers, of course, since no number is divisible by something which is larger than itself. For example, the GCD of 100 and something else could never be greater than 100, since 100 isn't divisible by anything greater than 100.

The one fact missing from the explanations above is this: the GCD of x and 8x + 1 must be 1. A quick explanation: if d is greater than 1, and d is a divisor of x, then d is a divisor of 8x. So the remainder will be 1 when 8x+1 is divided by d, since 8x+1 is 1 greater than an exact multiple of d; that is, 8x+1 cannot be divisible by d. So x and 8x+1 can't share a divisor besides 1.
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com

ianstewartgmat.com
Top
Legendary Member
Posts: 1799
Joined: Wed Dec 24, 2008 3:03 am
Thanked: 36 times
Followed by:2 members

by goelmohit2002 » Mon Jul 27, 2009 12:16 pm
Ian Stewart wrote:The GCD of two numbers can't be larger than either of the numbers, of course, since no number is divisible by something which is larger than itself. For example, the GCD of 100 and something else could never be greater than 100, since 100 isn't divisible by anything greater than 100.

The one fact missing from the explanations above is this: the GCD of x and 8x + 1 must be 1. A quick explanation: if d is greater than 1, and d is a divisor of x, then d is a divisor of 8x. So the remainder will be 1 when 8x+1 is divided by d, since 8x+1 is 1 greater than an exact multiple of d; that is, 8x+1 cannot be divisible by d. So x and 8x+1 can't share a divisor besides 1.
Awesome Ian !!!

Thanks a lot....

Just posted a similar reply using this concept.....on one of the threads in which you too participated....

Can you please look into the same at the below link...and tell if there is any flaw in my reasoning....

https://www.beatthegmat.com/gmat-prep-q- ... tml#174337
Top
Post new topic Post Reply
• Page 1 of 1