What is the gcd of a, b, and 3a+23b?
1) a=4. plug this in to get 4, b, 12+23b; If b=1, the gcd(4,1,35)=1. If b=4, the gcd(4,4,12+23(4))=4. INSUFFICIENT.
2) The greatest common divisor of a, b, and 23a+3b is 4. This implies that gcd(a,b)=4. If there were some divisor greater than 4, that a and b had in common, then it would also divide 23a+3b. But this would contradict the fact that gcd(a,b,23a+3b)=4. Hence, gcd(a,b)=4.
Back to the original question, the fact that gcd(a,b)=4 implies that 4 is a common divisor of a, b, and 3a+23b. But it also must be the GREATEST common divisor of a, b, 3a+23b, because if there were some common divisor greater than 4, it would contradict the fact that gcd(a,b)=4. SUFFICIENT
Ans: B
GCD.
This topic has expert replies
Source: Beat The GMAT — Data Sufficiency |
-
GmatMathPro
- GMAT Instructor
- Posts: 349
- Joined: Wed Sep 28, 2011 3:38 pm
- Location: Austin, TX
- Thanked: 236 times
- Followed by:54 members
- GMAT Score:770
-
vaibhavgupta
- Master | Next Rank: 500 Posts
- Posts: 416
- Joined: Tue Aug 30, 2011 2:18 pm
- Location: Delhi, India
- Thanked: 13 times
- Followed by:9 members
What if 3a+23b is not a factor of 4.. ?GmatMathPro wrote:What is the gcd of a, b, and 3a+23b?
1) a=4. plug this in to get 4, b, 12+23b; If b=1, the gcd(4,1,35)=1. If b=4, the gcd(4,4,12+23(4))=4. INSUFFICIENT.
2) The greatest common divisor of a, b, and 23a+3b is 4. This implies that gcd(a,b)=4. If there were some divisor greater than 4, that a and b had in common, then it would also divide 23a+3b. But this would contradict the fact that gcd(a,b,23a+3b)=4. Hence, gcd(a,b)=4.
Back to the original question, the fact that gcd(a,b)=4 implies that 4 is a common divisor of a, b, and 3a+23b. But it also must be the GREATEST common divisor of a, b, 3a+23b, because if there were some common divisor greater than 4, it would contradict the fact that gcd(a,b)=4. SUFFICIENT
Ans: B
-
GmatMathPro
- GMAT Instructor
- Posts: 349
- Joined: Wed Sep 28, 2011 3:38 pm
- Location: Austin, TX
- Thanked: 236 times
- Followed by:54 members
- GMAT Score:770
3a+23b is not a factor of 4, it's a multiple of 4. And this is because from statement 2, you know that a and b are both multiples of 4. That is a=4x for some integer x, and b=4y for some integer y. So, 3a+23b=3(4x)+23(4y)=4(3x+23y)
In words, if 4 is a factor of BOTH a and b, then it must be a factor of all linear combinations of a and b because we can definitely factor out a 4 from every term.
In words, if 4 is a factor of BOTH a and b, then it must be a factor of all linear combinations of a and b because we can definitely factor out a 4 from every term.
-
vaibhavgupta
- Master | Next Rank: 500 Posts
- Posts: 416
- Joined: Tue Aug 30, 2011 2:18 pm
- Location: Delhi, India
- Thanked: 13 times
- Followed by:9 members
Now, i get it! Thanks!GmatMathPro wrote:3a+23b is not a factor of 4, it's a multiple of 4. And this is because from statement 2, you know that a and b are both multiples of 4. That is a=4x for some integer x, and b=4y for some integer y. So, 3a+23b=3(4x)+23(4y)=4(3x+23y)
In words, if 4 is a factor of BOTH a and b, then it must be a factor of all linear combinations of a and b because we can definitely factor out a 4 from every term.
