If a and b are positive integers divisible by 6, is 6 the greatest com

Question

If a and b are positive integers divisible by 6, is 6 the greatest common divisor of a and b?

(1) a = 2b + 6

(2) a = 3b

Bunuel · Accepted Answer

If a and b are positive integers divisible by 6, is 6 the greatest common divisor of a and b? Given: a=6x and b=6y . Question: is GCD(a,b)=6 ? Now, If x and y share any common factor greater than 1, then GCD(a,b) will be more than 6, if not, then GCD(a,b) will be 6. (1) a=2b+6 --> 6x=2*6y+6 --> x=2y+1 --> x and y do not share any factor >1, as if they were we would be able to factor out if from 2y+1 . Sufficient. (2) a=3b --> clearly insufficient. Answer: A. There is also a general rule: if a and b are multiples of k and are k units apart from each other then k is greatest common divisor of a and b . For example if a and b are multiples of 7 and a=b+7 then 7 is GCD of a and b . So if we apply this rule to (1) a=2b+6 --> both a and 2b are multiples of 6 and are 6 apart, so GCD of a and 2b is 6, hence GCD of a and b is also 6. Sufficient. Similar questions: https://gmatclub.com/forum/what-is-the-g ... 09273.html https://gmatclub.com/forum/if-x-and-y-ar ... 01196.html Hope it helps.

mainhoon · Answer

note that a=3b does not mean that 6 will be the gcd. example 6, 18 is 6, but 12, 36 is 12 not suff

for a =2b+6= 2(b+3); take b=6,a=18, gcd =6 ; take b=12,a=30; gcd=6; take b=18,a=42; gcd=6 suff

for an algebraic proof: a=6r, b=6s
2. a=3b means 6r=18s or r=3s; a=6s b=18s; cannot conclude about gcd
a=2b+6 means r=2s+1; a=6(2s+1); b=6s no common factors; you can conclude that 6 will be gcd.

svalan · Answer

Hi Bunuel, could you kindly elaborate on the following statement:

"x=2y+1 --> x and y do not share any factor >1, as if they were we would be able to factor out if from 2y+1. Sufficient."

I'm obviously missing some fundamental insight, but I don't understand why not being able to factor something out of the 2y+1 means that 6 is the GCD.

Thanks!

Bunuel · Answer

We have that  a=6x  and  b=6y .

Consider two cases: 
1.  x  and  y  share some common factor >1: for example  x=2  and  y=4  then  a=12  and  b=24  -->  GCD(a,b)=12>6 ;
2.  x  and  y  DO NOT share any common factor >1: for example  x=5  and  y=2  then  a=30  and  b=12  -->  GCD(a,b)=6 .

From (1) we have that -->  x=2y+1  -->  x  is one more than multiple of  y . For example:  x=3  and  y=1  OR  x=5  and  y=2  OR  x=7  and  y=3  ... as you can see in all these cases x and y do not share any common factor more than 1. Now, as we concluded above if  x  and  y  DO NOT share any common factor >1, then  GCD(a,b)=6 .

Hope it's clear.

svalan · Answer

Crystal clear, thanks so much!

Runner2 · Answer

Perfect explanation

Saurajm · Answer

But if a and b are both divisible of 6, means that both are even, therefore at least both of them should be divisible by 2.... I am right????? I do not understand why (1) is valid... thanks!!

Bunuel · Answer

Yes, both are divisible by 6, which means that they are divisible by 2 and 3. Next, we have that a=6x and b=6y . Consider two cases: 1. x and y share some common factor >1: for example x=2 and y=4 then a=12 and b=24 --> GCD(a,b)=12>6 ; 2. x and y DO NOT share any common factor >1: for example x=5 and y=2 then a=30 and b=12 --> GCD(a,b)=6 . From (1) we have that --> x=2y+1 --> x is one more than multiple of y . For example: x=3 and y=1 OR x=5 and y=2 OR x=7 and y=3 ... as you can see in all these cases x and y do not share any common factor more than 1. Now, as we concluded above if x and y DO NOT share any common factor >1, then GCD(a,b)=6 . Or another way: b=6y and a=6(2y+1) . 2y and 2y+1 are consecutive integers and consecutive integers do not share any common factor 1. As 2y has all factors of y then y and 2y+1 also do not share any common factor but 1, which means that 6 must GCD of a and b Similar questions to practice: what-is-the-greatest-common-factor-of-x-and-y-1-x-and-y-are-109273.html x-and-y-are-positive-integers-such-that-x-8y-12-what-is-the-126743.html Hope it helps.

pavanpuneet · Answer

Hi Bunuel, Can you explain the following rule with few examples.

Given: and . Question: is ? Now, If x and y share any common factor >1then GCD (a,b) will be more than 6 if not then GCD (a,b) will be 6.

Bunuel · Answer

Sure. Both  a  and  b  are multiples of 6 -->  a=6x  and  b=6y . Consider two cases:

A.  x  and  y  do not share any common factor >1, for example  a=6*2=12  and  b=6*3=18  --> GCD(a,b)=6. As you can see 2 and 3 did not contribute any common factor to the GCD;

B.  x  and  y  share some common factor >1, for example  a=6*2=12  and  b=6*4=24  --> GCD(a,b)=12, here 2 and 4 contributes common factor 2 to the GCD.

Hope it's clear.

WoundedTiger · Answer

Given a and b are positive integers divisible by 6

From st 1, we have a = 2b+ 6 
b is of the form b= 6c where c is a positive integer

therefore we have a = 2*6c+6 ----> a= 6 (2c+1)
b= 6c

Now HCF of a and b will be 6 as 
a= 2*3*(2c+1)
b=2*3
Only common factor is 6

So, Ans is A alone sufficient. We can remove options B, C and E as possible answers

Not st 2 says a= 3b 
taking b = 6c we have a=18c

a= 2*3^2*c
b=2*3 c
HCF will be 2*3*c that is 6c

Now if c=1 then 6 is a the HCF of both a and b
but if c=2 then 12 is HCF
Since 2 ans choices are possible.

Ans will be A to this Question

kpali · Answer

Question:
6 * x =a and 6 * y =b
we need to find if 6 is the GCD? YES or NO question.
so, basically if we can find a single common factor in x and y, thats it its not a GCD, or if we cant find one then that should also work for us.

(1) a = 2b + 6

6x=12y + 6

x = 2y +1 =>No matter what you do, this will always result in an no common factor.

Thus 6 is the only GCD =>Sufficient

(2) a = 3b

6x = 18y
x=3y

Take y=8, and Y=2 =>This is clearly Not sufficient.

Ans: A

shankar245 · Answer

Hi Bunuel,

Can you please explain

x and y do not share any factor >1, as if they were we would be able to factor out if from 2y+1. Sufficient.

so if we have x=2(2y+1) then x does have a factor of 2,but how do we know about the factors of y.

Bunuel · Answer

x=2y+1 means that x and 2y are co-prime (x and 2y do not share any common factor but 1), which, on the other hand, means that x and y are co-prime. How else? If x and 2y do not share any common factor greater than 1, how can x and y share any common factor greater than 1?

earnit · Answer

It would be great if one could find more questions involving GCD/GCF as they seem to be little tricky more often than not.

Bunuel · Answer

Check similar questions to practice: what-is-the-greatest-common-factor-of-x-and-y-109273.html x-and-y-are-positive-integers-such-that-x-8y-12-what-is-the-126743.html DS Divisibility/Multiples/Factors questions to practice: search.php?search_id=tag&tag_id=354 PS Divisibility/Multiples/Factors questions to practice: search.php?search_id=tag&tag_id=185 For more browse our QUESTION BANKS . Hope it helps.

hatemnag · Answer

If x and 2y do not share any common factor greater than 1, how can x and y share any common factor greater than 1?
Please Bunuel clarify this comment more. what does it mean.
another question is that how frequently DS questions of divisibility come in GMAT test ?

Bunuel · Answer

Let me ask you: if x and y shared any common factor but 1, would x and 2y be co-prime?

camilles · Answer

Thanks for the explanation.

Still I do not understand why statement 2 is not sufficient. My reasoning is this one:
- for 6 to be GCD(a,b) then "a" and "b" must be multiple of 6 but "a" must also be equal to b+6 right?
- The only way to have a=3b and a=b+6 is for b=3 and a=9. However as b/6 must result in an integer we know that "a" cannot be equal to 3b, hence it is enough to say that 6 is NOT the gcd of (a,b). Therefore statement 2 is sufficient to answer the question.

Can you please tell me where my reasoning is flawed?

If a and b are positive integers divisible by 6, is 6 the greatest com

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Data Sufficiency (DS) Questions

If a and b are positive integers divisible by 6, is 6 the greatest com

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards