If x and y are positive integers, what is greatest common divisor of x and y?
1) 2x+y=23
2) 4x-3y=1
GCD
This topic has expert replies
-
- Master | Next Rank: 500 Posts
- Posts: 131
- Joined: Fri Jun 18, 2010 10:19 am
- Location: New York, NY
- Thanked: 10 times
I get B.
We're asked for the greatest common divisor, which can also be referred to as the greatest common factor. From the question, we only know that x and y are both positive integers.
STATEMENT 1: 2x + y = 23. INSUFFICIENT because x could be 1 and y could be 21, in which case the GCF is 1. But x could also be 3, in which case y is 18, and the GCF is 3.
STATEMENT 2: 4x-3y=1. I'm not sure if there's a more elegant solution, but I just plugged in numbers to solve again. 4(1) - 3(1) = 1. In this case, the GCF is 1. 4(7) - 3(9) = 1. In this case, too, the GCF is 1. 4(10) - 3(13) = 1. And, once more, the GCF is 1.
We're asked for the greatest common divisor, which can also be referred to as the greatest common factor. From the question, we only know that x and y are both positive integers.
STATEMENT 1: 2x + y = 23. INSUFFICIENT because x could be 1 and y could be 21, in which case the GCF is 1. But x could also be 3, in which case y is 18, and the GCF is 3.
STATEMENT 2: 4x-3y=1. I'm not sure if there's a more elegant solution, but I just plugged in numbers to solve again. 4(1) - 3(1) = 1. In this case, the GCF is 1. 4(7) - 3(9) = 1. In this case, too, the GCF is 1. 4(10) - 3(13) = 1. And, once more, the GCF is 1.
- anshumishra
- Legendary Member
- Posts: 543
- Joined: Tue Jun 15, 2010 7:01 pm
- Thanked: 147 times
- Followed by:3 members
There could be infinitely many integral solutions for 4x-3y =1 (which is also the equation of a straight line with slope 4/3)aleph777 wrote:
STATEMENT 2: 4x-3y=1. I'm not sure if there's a more elegant solution, but I just plugged in numbers to solve again. 4(1) - 3(1) = 1. In this case, the GCF is 1. 4(7) - 3(9) = 1. In this case, too, the GCF is 1. 4(10) - 3(13) = 1. And, once more, the GCF is 1.
x=1, y=1
x=4, y=5
x=10, y=13
x=13, y=17
and so on......
So, the answer should be [spoiler]"C"[/spoiler] as, combining the two equations we get two distinct equations in x and y, which ensures a single value for the GCF.
Thanks
Anshu
(Every mistake is a lesson learned )
Anshu
(Every mistake is a lesson learned )
-
- Master | Next Rank: 500 Posts
- Posts: 131
- Joined: Fri Jun 18, 2010 10:19 am
- Location: New York, NY
- Thanked: 10 times
Anshumishra,
I thought C at first, too, but then I went back and tried to plug in numbers using just B. Since we're looking for the GCF rather than two individual values, in every case, the GCF of x and y was 1.
But you're saying that, because statement 2 leaves the possible x and y values infinitely open, we can't say the GCF will always be 1?
I thought C at first, too, but then I went back and tried to plug in numbers using just B. Since we're looking for the GCF rather than two individual values, in every case, the GCF of x and y was 1.
But you're saying that, because statement 2 leaves the possible x and y values infinitely open, we can't say the GCF will always be 1?
- anshumishra
- Legendary Member
- Posts: 543
- Joined: Tue Jun 15, 2010 7:01 pm
- Thanked: 147 times
- Followed by:3 members
You are right Aleph777,aleph777 wrote:Anshumishra,
I thought C at first, too, but then I went back and tried to plug in numbers using just B. Since we're looking for the GCF rather than two individual values, in every case, the GCF of x and y was 1.
But you're saying that, because statement 2 leaves the possible x and y values infinitely open, we can't say the GCF will always be 1?
Although there are infinitely many solutions however the pattern of few of the solutions selected suggests that the gcd is fixed (i.e. it is 1).
Hence, "B" looks good.
Thanks
Anshu
(Every mistake is a lesson learned )
Anshu
(Every mistake is a lesson learned )
-
- Legendary Member
- Posts: 759
- Joined: Mon Apr 26, 2010 10:15 am
- Thanked: 85 times
- Followed by:3 members
hi guys
imo the answer is D
you proved that 2 st is suff
but i dare say that 1 st is suff as well
(1) 2x+y=23, considering that x,y are +ve integers, we can numerate all possible pairs for x,y and they will be co-prime in all cases so GCD is 1
(x,y)=(1,21), (2,19) (3,17) (4,15)...... and so on
imo the answer is D
you proved that 2 st is suff
but i dare say that 1 st is suff as well
(1) 2x+y=23, considering that x,y are +ve integers, we can numerate all possible pairs for x,y and they will be co-prime in all cases so GCD is 1
(x,y)=(1,21), (2,19) (3,17) (4,15)...... and so on
-
- Legendary Member
- Posts: 1337
- Joined: Sat Dec 27, 2008 6:29 pm
- Thanked: 127 times
- Followed by:10 members
LCM (lowest common multiple)*GCD=x*y, GCD=xy/LCM;
x,y {integers} >0, Find GCD-?
st(1) 2x+y=23, y can be 21, 19, 17... Not Sufficient
st(2) 4x-3y=1, y can be 1, 5, ...Not Sufficient
Combined st(1&2): 2x+y=23 and 4x-3y=1 --> 4x-3*(23-2x)=1, 4x-69+6x=1, x=7 and y=9
x*y=63, LCM (7;9)=63 --> GCD=63/63=1/ Sufficient.
IOM C
x,y {integers} >0, Find GCD-?
st(1) 2x+y=23, y can be 21, 19, 17... Not Sufficient
st(2) 4x-3y=1, y can be 1, 5, ...Not Sufficient
Combined st(1&2): 2x+y=23 and 4x-3y=1 --> 4x-3*(23-2x)=1, 4x-69+6x=1, x=7 and y=9
x*y=63, LCM (7;9)=63 --> GCD=63/63=1/ Sufficient.
IOM C
yellowho wrote:If x and y are positive integers, what is greatest common divisor of x and y?
1) 2x+y=23
2) 4x-3y=1
Hi!
I think that the answer is D
Solution: If GCD(x;y)=d then in both statements LHS is divisible by d. Hence, according to the II statement 1 is divisible by d, d=1. I statement is also true. If LHS is divisible by d, then RHS is also divisible by d. Hence, 23 is divisible by d, d=1 or d=23. But we are given that x and y are positive integers. That's why both of them less than 23. So, d=1.
I think that the answer is D
Solution: If GCD(x;y)=d then in both statements LHS is divisible by d. Hence, according to the II statement 1 is divisible by d, d=1. I statement is also true. If LHS is divisible by d, then RHS is also divisible by d. Hence, 23 is divisible by d, d=1 or d=23. But we are given that x and y are positive integers. That's why both of them less than 23. So, d=1.
-
- Senior | Next Rank: 100 Posts
- Posts: 79
- Joined: Mon Sep 15, 2008 5:54 pm
- Thanked: 3 times
IMO D
St(1)
makes 2x even so y is odd.
the largest y can be is 21. y can be odd from 1thru21.
The only odd multiples of other odd numbers in that range are 21(for 7and 3),15(for 5and 3), 9(3 and 3). None fit the bill so this is sufficient for GCF as 1.
St(2)
Rewrite as 3y+1=4x
The Values that fit the bill for this equation are :
y(=1+4x): 1,5,9,13,17,21,25,29,33,37,etc.
x(=1+3x): 1,4,7,10,13,16,19,22,25,28,etc.
I didn't write all these values on paper but my estimate for this one is that it'll never have another common factor.
Sufficient
3x+1 and 4x+1, can someone prove this?
Therefore, my answer for this is D.
St(1)
makes 2x even so y is odd.
the largest y can be is 21. y can be odd from 1thru21.
The only odd multiples of other odd numbers in that range are 21(for 7and 3),15(for 5and 3), 9(3 and 3). None fit the bill so this is sufficient for GCF as 1.
St(2)
Rewrite as 3y+1=4x
The Values that fit the bill for this equation are :
y(=1+4x): 1,5,9,13,17,21,25,29,33,37,etc.
x(=1+3x): 1,4,7,10,13,16,19,22,25,28,etc.
I didn't write all these values on paper but my estimate for this one is that it'll never have another common factor.
Sufficient
3x+1 and 4x+1, can someone prove this?
Therefore, my answer for this is D.
-
- Master | Next Rank: 500 Posts
- Posts: 233
- Joined: Wed Aug 22, 2007 3:51 pm
- Location: New York
- Thanked: 7 times
- Followed by:2 members
OA is [spoiler][/spoiler]. Can an expert please address this.
[quote="cyrwr1"]IMO D
St(1)
makes 2x even so y is odd.
the largest y can be is 21. y can be odd from 1thru21.
The only odd multiples of other odd numbers in that range are 21(for 7and 3),15(for 5and 3), 9(3 and 3). None fit the bill so this is sufficient for GCF as 1.
St(2)
Rewrite as 3y+1=4x
The Values that fit the bill for this equation are :
y(=1+4x): 1,5,9,13,17,21,25,29,33,37,etc.
x(=1+3x): 1,4,7,10,13,16,19,22,25,28,etc.
I didn't write all these values on paper but my estimate for this one is that it'll never have another common factor.
Sufficient
3x+1 and 4x+1, can someone prove this?
Therefore, my answer for this is D.[/quote]
[quote="cyrwr1"]IMO D
St(1)
makes 2x even so y is odd.
the largest y can be is 21. y can be odd from 1thru21.
The only odd multiples of other odd numbers in that range are 21(for 7and 3),15(for 5and 3), 9(3 and 3). None fit the bill so this is sufficient for GCF as 1.
St(2)
Rewrite as 3y+1=4x
The Values that fit the bill for this equation are :
y(=1+4x): 1,5,9,13,17,21,25,29,33,37,etc.
x(=1+3x): 1,4,7,10,13,16,19,22,25,28,etc.
I didn't write all these values on paper but my estimate for this one is that it'll never have another common factor.
Sufficient
3x+1 and 4x+1, can someone prove this?
Therefore, my answer for this is D.[/quote]
- GMATGuruNY
- GMAT Instructor
- Posts: 15539
- Joined: Tue May 25, 2010 12:04 pm
- Location: New York, NY
- Thanked: 13060 times
- Followed by:1906 members
- GMAT Score:790
Statement 1: 2x + y = 23yellowho wrote:If x and y are positive integers, what is greatest common divisor of x and y?
1) 2x+y=23
2) 4x-3y=1
2x + y = prime.
If x and y share a factor other than 1, then their sum will also share that factor and thus will not be prime. Since the given sum of 23 is prime, x and y cannot share a factor other than 1.
To illustrate:
6+15 = 21. Since 3 is factor of both 6 and 15, 3 is also a factor of their sum of 21, resulting in a sum that is not prime.
10+25 = 35. Since 5 is a factor of both 10 and 25, 5 is also a factor of their sum of 35, resulting in a sum that is not prime.
Thus, in order for the the sum of 2x + y to be a prime number, the greatest common factor of x and y must be 1.
Sufficient.
Statement 2: 4x - 3y = 1
Since the difference between 4x and 3y is 1, we know that 4x and 3y are consecutive integers.
Consecutive integers are coprimes: they share no factor other than 1.
Thus, x and y cannot share a factor other than 1.
To illustrate:
If x and y were each a multiple of 2, then 4x and 3y would each be a multiple of 2, making it impossible for 4x and 3y to be consecutive integers.
If x and y were each a multiple of 3, then 4x and 3y would each be a multiple of 3, making it impossible for 4x and 3y to be consecutive integers.
Thus, since 4x and 3y are consecutive integers, the greatest common factor of x and y must be 1.
Sufficient.
The correct answer is D.
Last edited by GMATGuruNY on Fri Feb 18, 2011 7:48 am, edited 4 times in total.
Private tutor exclusively for the GMAT and GRE, with over 20 years of experience.
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.
As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.
For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.
As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.
For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3
- ankur.agrawal
- Master | Next Rank: 500 Posts
- Posts: 261
- Joined: Wed Mar 31, 2010 8:37 pm
- Location: Varanasi
- Thanked: 11 times
- Followed by:3 members
U r Awesome .Thanks for the gr8 insight.
GMATGuruNY wrote:Statement 1: 2x + y = 23yellowho wrote:If x and y are positive integers, what is greatest common divisor of x and y?
1) 2x+y=23
2) 4x-3y=1
The following ordered pairs satisfy 2x + y = 23:
1, 21
2, 19
3, 17
4, 15
5, 13
6, 11
7, 9
8, 7
9, 5
10, 3
11, 1
In each ordered pair, the greatest common factor is 1.
Sufficient.
Statement 2: 4x - 3y = 1
Since the difference between 4x and 3y is 1, we know that 4x and 3y are consecutive integers.
Consecutive integers are coprimes: they share no factor other than 1.
Thus, x and y cannot share a factor other than 1.
To illustrate:
If x and y were each a multiple of 2, then 4x and 3y would each be multiple of 2, making it impossible for 4x and 3y to be consecutive integers.
If x and y were each a multiple of 3, then 4x and 3y would each be a multiple of 3, making it impossible for 4x and 3y to be consecutive integers.
Thus, since 4x and 3y are consecutive integers, the greatest common factor of x and y must be 1.
Sufficient.
The correct answer is D.