What is the greatest common divisor ?

Question

Hi All,

Can someone please tell how to solve this question ?

If x and y are positive integers such that x = 8y +12. What is the greatest common divisor of x and y ?

1) x = 12u, where u is an integer.
2) y = 12z, where z is an integer.

OA = B.

Thanks
Mohit

yogami · Answer

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

goelmohit2002 · Answer

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....

goelmohit2002 · Answer

Can someone please help to solve this question ?

ogbeni · Answer

@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......

goelmohit2002 · Answer

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.....

Ian Stewart · Answer

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

goelmohit2002 · Answer

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

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

What is the greatest common divisor ?

GMAT/MBA Expert

Chicago Booth

GMAT Course Reviews

Admissions Consulting Reviews

FREE GMAT PREP RESOURCES

GMAT PREP DEAL TRACKER