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

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!

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.

Crystal clear, thanks so much!

Perfect explanation

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

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.

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.

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.

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

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

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.

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?

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

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.

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 ?

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

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?