In x and y are positive integers such that x = 8y + 12

[me.parashar]

So 12 is a common divisor of x and y. But is it the greatest common divisor?

RULE: If one number is b units away from another number, and b is a factor of both numbers, the greatest common factor of the two numbers is b. (If you want to really understand this, then think about why. Otherwise, just remember the rule.)

x (one number) is 12 units away from 8y (another number). 12 is a factor of x and 8y. Therefore, 12 is the GCF of x and 8y. The GCF of x and y can’t be bigger than the GCF of x and 8y. Thus, we can be assured that 12 is the GCF of x and y. Statement (2) alone is SUFFICIENT.

Hi Stacey, In your reasoning above, shouldn't the same logic be applicable to first statement.
x = 12u
8y = 12u - 12 = 12*(u - 1)
so both x and 8y have 12 as a factor.
Now, by the rule, x and 8y are also 12 units apart, so x and 8y have 12 as a GCF.

The GCF of x and y can’t be bigger than the GCF of x and 8y. Thus, we can be assured that 12 is the GCF of x and y. Statement (2) alone is SUFFICIENT.

By the same logic, Statement (1) alone is SUFFICIENT.

Please could you explain where my reasoning is going wrong.

Thanks

[RonPurewal]

Please could you explain where my reasoning is going wrong.

Thanks

the difference lies in the one step that you left out in considering stacey's explanation: the fact that, in the second statement, both x and y are definitely multiples of 12.
(you know this about y because you're explicitly given that y = 12z; you know this about x because x = 8(12z) + 12, from which you can factor out 12.)

in the first statement, you know that x is a multiple of 12 (because you're explicitly told that it is), but you don't know that y is a multiple of 12.
you know that 8y is a multiple of 12, but that's not the same thing at all.
so, even though you are correct that 12 is the gcf of x and 8y in this case, you're no longer able to take the next logical leap and make a statement about y itself.

--

as in many, many other DS problems, if you are not crystal clear on the theory here, you should just test cases and see what happens.
even though this problem is incredibly obnoxious to solve with theory/algebra, it's fairly straightforward if you test cases.

TESTING CASES

STATEMENT (1)
for this statement, we need to start with x's that are multiples of 12. per the stated restrictions, we'll only keep the ones that give y a positive integer value (in the equation x = 8y + 12).
* x = 12: this would give y = 0. reject.
* x = 24: this would give y = 12/8 = 1.5. reject.
* x = 36: this would give y = 3. in this case, the gcf is 3.
* x = 48: this would give y = 36/8 = 4.5. reject.
* x = 60: this would give y = 6. in this case, the gcf is 6.
done; not sufficient.

STATEMENT (2)
this time, we start with y's that are multiples of 12, and then find x (according to the given formula x = 8y + 12). we won't need to reject any cases this time, because 8(integer) + 12 is always going to be an integer.
also notice that there's no need to do out the arithmetic; we can just leave products as products, since that's more conducive to finding gcf's anyway.
* y = 12: this gives x = 8(12) + 12 = 9*12. here, the gcf is 12.
* y = 24: this gives x = 8(24) + 12 = 16*12 + 12 = 17*12. in other words, x = 2*12 and y = 17*12, so the gcf is 12.
* y = 36: this gives x = 8(36) + 12 = 24*12 + 12 = 25*12. in other words, x = 3*12 and y = 25*12, so the gcf is 12.

at this point, you should be starting to get convinced. (i've never seen an instance of a "fake pattern" in an official DS problem -- once the same thing happens a few times in a row and you see an obvious-looking pattern, you should be able to trust it.) so, sufficient.

[angierch]

Hi Jamie,

Is it possible to explain how we conclude that if the GCD of x and 8y is 12, then the GCD of x and y is 12 as well? I understand that the GCD of x and y can't be greater than the GCD of x and 8y, but why couldn't the GCD of x and y be 6 for example? I would like to understand the theory behind this rather than prooving it by plugging numbers. I think understanding the theory will help me solving another similar question in the GMAT.

Thanks so much!
Angelica

[MohitS94]

Given (2), we definitely know that 12 in a factor of y. And then replacing this value of y in the given equation,
x = 8(12z) + 12 => x = 12(8z +1)
Clearly 12 is a factor of x as well.

The only question remaining was whether it is the greatest.

I wanted to attempt a proof of the theorem given here. Came up with the following.

Assume A, B, d, x and y are positive integers such that,
A=xd
B=yd
and, A-B=d

Substituting the values from the first and second into the third.
xd - yd = d
or, x - y = 1
or, x = y + 1

This means x and y are consecutive numbers. And two consecutive numbers are always co-prime, meaning they do not have any factors in common apart from 1.

Therefore, d is the greatest common factor of A and B.

Btw, I think Tim's proof is way more elegant and "complete" since to prove that two consecutive numbers are co-prime, we would need to use a similar proof by contradiction. His proof leaves nothing more to be desired. :)

[RonPurewal]

Hi Jamie,

Is it possible to explain how we conclude that if the GCD of x and 8y is 12, then the GCD of x and y is 12 as well?

not true.
if x = 12 and y = 3, then the greatest common factor of x and 8y is 12, but the greatest common factor of x and y is 3.

can you please quote the text to which you're replying? this is a very long thread, so, unless you're replying to the thread directly above yours, that's an essential courtesy.
thanks.

[NinaP494]

let x = y - b, all integers. assume there is some integer a > b such that a is a factor of both x and y. then x = a*m and y = a*n for some integers m and n. now a*m = a*n-b or b = a(n-m). by this logic, a is a factor of b, which contradicts our assumption that a > b. thus there is no integer a > b such that a is a factor of both x and y.

Loved loved loved the proof. I could never for the life of me remember this rule. Now I will never forget it.

[RonPurewal]

.

[HaroonM483]

Therefore, y must be a multiple of 3 and 3 is a divisor of y. 3 might be the greatest common divisor of x and y. But y might have other divisors too (e.g., 6 or 12). Insufficient.

Hi!

Digging up an old post here, apologies!

I am trying to make sense of this problem. The only issue I have is:

How from (1) do we know y might have other divisors, other than 3?

Simplifying (1): I get

x = (4)(3)(u); y = (3)(1/2)(u-1)

So 3 appears to be the GCD (x,y) from the above, but I am uncertain as to how I make the next step to -> This is insufficient, as a value for GCD, or is it just that from (2) 12>3 therefore I can eliminate (1) on this basis?

Thanks in advance.

H

[Sage Pearce-Higgins]

No worries about opening an old thread - this problem is still current in the GMAT Prep tests. I agree that it's tough to see that, according to statement (1), x and y could have other divisors. In fact, I wouldn't trust myself to use that logic in a test. I prefer the method of simply listing out cases to find a pattern. If you make a table with values of x and y, it would look like this:
y 1 2 3 4 5 6 ...
x 20 28 36 44 52 60 ...
If we follow statement (1), then we know that x is a multiple of 12, so, from these examples, it could be 36 or 60. For these cases we can see that the common factor of x and y is 3 for the first case and 6 for the second, meaning that we can get different answers to the question and statement (1) is not sufficient.

This approach (of testing cases) wins out for me because it's simpler. Even if I understood the more theoretical approach, I'd be unsure if I could actually apply that logic under pressure in a new situation.