Author 
Message 
TAGS:

Hide Tags

Manager
Joined: 04 Feb 2011
Posts: 59
Location: US

Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
08 Feb 2011, 01:43
Question Stats:
79% (00:27) correct 21% (00:27) wrong based on 766 sessions
HideShow timer Statistics
Which of the following CANNOT be the greatest common divisor of two positive integers x and y? A. 1 B. x C. y D. xy E. x+y
Official Answer and Stats are available only to registered users. Register/ Login.



Math Forum Moderator
Joined: 20 Dec 2010
Posts: 1901

Re: problem solving [#permalink]
Show Tags
08 Feb 2011, 02:55
GCD of two postive numbers will always be less than or equal to the smaller of the two numbers. If x and y are two +ve integers. \(if (x < y)\) \(GCD(x,y) <= x\) \(if (y < x)\) \(GCD(x,y) <= y\) \(if (y = x)\) \(GCD(x,y) = y = x\) In any case; GCD must be less than the sum of the two numbers GCD(x,y) < (x+y) Ans: "E"
_________________
~fluke
GMAT Club Premium Membership  big benefits and savings



Math Expert
Joined: 02 Sep 2009
Posts: 46090

Re: problem solving [#permalink]
Show Tags
08 Feb 2011, 03:28



Senior Manager
Joined: 21 Mar 2010
Posts: 292

Re: problem solving [#permalink]
Show Tags
09 Feb 2011, 10:22
E.
X+y will be greater than either x or y and hence it cannot be the answer.



GMAT Tutor
Joined: 24 Jun 2008
Posts: 1345

Re: Could you explain? [#permalink]
Show Tags
26 Nov 2011, 07:15
The greatest common divisor of x and y must be a divisor of x, so it can't be larger than x. Since x+y is larger than x, it cannot be the greatest common divisor of x and y.
_________________
GMAT Tutor in Toronto
If you are looking for online GMAT math tutoring, or if you are interested in buying my advanced Quant books and problem sets, please contact me at ianstewartgmat at gmail.com



Manager
Joined: 13 Feb 2012
Posts: 141
Location: Italy
Concentration: General Management, Entrepreneurship
GPA: 3.1
WE: Sales (Transportation)

Re: Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
24 Jul 2012, 10:42
Manhattan's way of visualizing the GCF comes in handy in this type of question. Even if you do not recall by theory that the GCF cannot be greater than either terms, you can figure that out.
_________________
"The Burnout"  My Debrief
Kudos if I helped you
Andy



Intern
Joined: 01 Aug 2006
Posts: 34

Re: Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
07 Feb 2014, 21:49
Which of the following CANNOT be the greatest common divisor of two positive integers x and y?
method 1: use examples/counter examples. A. 1 (x=2;y=3) B. x (x=2; y = 4) C. y (x=4; y = 2) D. xy (x = 4; y =2) E. x+y > NOT POSSIBLE.
Concept: Factors of a number are always less than or equal to that number. HCF of x and y can never be greater than the smaller number.



eGMAT Representative
Joined: 04 Jan 2015
Posts: 1484

Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
27 Apr 2015, 05:50
Bunuel wrote: Bumping for review and further discussion. Hi Everyone! Here's a question to further test your understanding of the concept of GCD: If A and B are distinct positive integers greater than 1 such that the GCD of A and B is A, then which of the following must be true?
(A) A is a prime number (B) A and B have the same prime factors. (C) A and B have the same evenodd nature (D) All the factors of B are divisible by A (E) The LCM of A and B is BWill post the solution in this thread on May 1, 2015. Till then, happy solving! Regards Japinder
_________________
 '4 out of Top 5' Instructors on gmatclub  70 point improvement guarantee  www.egmat.com



Current Student
Joined: 29 Mar 2015
Posts: 77
Concentration: Strategy, Operations
WE: Research (Other)

Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
27 Apr 2015, 11:56
EgmatQuantExpert wrote: Bunuel wrote: Bumping for review and further discussion. Hi Everyone! Here's a question to further test your understanding of the concept of GCD: If A and B are distinct positive integers greater than 1 such that the GCD of A and B is A, then which of the following must be true?
(A) A is a prime number (B) A and B have the same prime factors. (C) A and B have the same evenodd nature (D) All the factors of B are divisible by A (E) The LCM of A and B is BWill post the solution in this thread on May 1, 2015. Till then, happy solving! Regards Japinder I think B, C and E are valid for the above question.
_________________
If you like my post, Pl. do not hesitate to press kudos!!!!
Q51 on GMAT  PM me if you need any help with GMAT QUANTS!!!



eGMAT Representative
Joined: 04 Jan 2015
Posts: 1484

Re: Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
01 May 2015, 06:13
EgmatQuantExpert wrote: Bunuel wrote: Bumping for review and further discussion. Hi Everyone! Here's a question to further test your understanding of the concept of GCD: If A and B are distinct positive integers greater than 1 such that the GCD of A and B is A, then which of the following must be true?
(A) A is a prime number (B) A and B have the same prime factors. (C) A and B have the same evenodd nature (D) All the factors of B are divisible by A (E) The LCM of A and B is BWill post the solution in this thread on May 1, 2015. Till then, happy solving! Regards Japinder The correct answer is Option E.PFB the correct solution for this question: We are given that A and B are distinct positive integers greater than 1 such that the GCD of A and B is A The important thing to note is that the question is asking about must be true statements. Must be true statements are those that will hold for all possible values of A and B, without exception. So, our approach here will be to see if we can find any exceptions to the 5 given statements. Let's see. (A) A is a prime numberConsider A = 20 and B = 60. In this case, GCD(A,B) = A but A is not a prime number. Since we have found an exception to Statement A, it is clearly not a must be true statement. (B) A and B have the same prime factors.Once again, consider the case of A = 20 and B= 60. The prime factors of A are 2 and 5. The prime factors of B are 2, 3 and 5. So, clearly Statement B doesn't hold true for all possible values of A and B, and therefore, cannot be a must be true statement. (C) A and B have the same evenodd natureConsider A = 3 and B = 6. Here too, GCD(A,B) = A but the evenodd nature of A and B is opposite. So, Statement C is ruled out as well. (D) All the factors of B are divisible by A In the case of A= 20 and B = 60, 15 is a factor of B that is not divisible by A. Similarly, in the case of A = 3 and B = 6, 1 is a factor of B that is not divisible by A The existence of these exceptions indicates that Statement D is not a must be true statement. (E) The LCM of A and B is BWe know that LCM(A,B)*GCD(A,B) = A*B . . . (1) Given: GCD(A,B) = A . . . (2) On substituting (2) in (1), we get: LCM(A,B) = B Therefore, Statement E will always be true, for all values of A and B. Thanks and Best Regards Japinder
_________________
 '4 out of Top 5' Instructors on gmatclub  70 point improvement guarantee  www.egmat.com



eGMAT Representative
Joined: 04 Jan 2015
Posts: 1484

Re: Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
01 May 2015, 06:19
nailgmat2015 wrote: I think B, C and E are valid for the above question.
Dear nailgmat2015Thank you for attempting this question. Please go through the solution posted above and let me know if you have any doubts about it. See you around! Japinder
_________________
 '4 out of Top 5' Instructors on gmatclub  70 point improvement guarantee  www.egmat.com



Current Student
Joined: 29 Mar 2015
Posts: 77
Concentration: Strategy, Operations
WE: Research (Other)

Re: Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
01 May 2015, 07:25
EgmatQuantExpert wrote: nailgmat2015 wrote: I think B, C and E are valid for the above question.
Dear nailgmat2015Thank you for attempting this question. Please go through the solution posted above and let me know if you have any doubts about it. See you around! Japinder Thanks Jaspinder... I want to clarify two things which are what is the level of this question? and how to approach number system questions (I mean substituting values and working through is the best way to approach questions)?
_________________
If you like my post, Pl. do not hesitate to press kudos!!!!
Q51 on GMAT  PM me if you need any help with GMAT QUANTS!!!



eGMAT Representative
Joined: 04 Jan 2015
Posts: 1484

Re: Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
04 May 2015, 04:08
nailgmat2015 wrote:
Thanks Jaspinder...
I want to clarify two things which are what is the level of this question? and how to approach number system questions (I mean substituting values and working through is the best way to approach questions)?
Dear nailgmat2015Thank you for your questions. PFB my response. 1. This question is of GMAT 650 difficulty level. That said, I don't think the difficultylevel of a question is an important number. During the preparation stage, one should focus on the learning that one can glean from a question. And, every question that can teach you something  whether a conceptual point or a takeaway on how to attempt questions better  is an important question. By focusing in this manner on i) building concepts ii) learning to solve questions methodically in a stepbystep manner iii) learning from the mistakes that one makes along the way even the questions of the GMAT 700+ difficulty level will start seeming easy to you. 2. I am not too big a fan of solving questions by substituting numbers. This approach certainly appears appealing at the first look because it seemingly allows you to bypass conceptual understanding. And precisely there lies the problem with this approach  if, during your preparation, you solve questions by substituting numbers, you're depriving yourself of an opportunity to hone your conceptual understanding. I always advise my students to work through questions from the first principles. Since your question was specifically about Number Properties, I can actually share with you a tangible sample of what I mean: Our Number Properties Live Classroom session is a free session and likewise, its recording too is freely accessible by all. Please click here to go to the recording (the video takes about 45 seconds to load). The Number Properties part begins from the 20th minute onwards. In this session, you'll find both basic and very advanced questions from EvenOdd numbers, Prime Numbers and LCMGCD. And, you'll see for yourself how even the most difficult Number Properties questions can be solved by applying, in a stepbystep manner, the basic concepts that you already know. I hope you found this discussion useful. Please let me know if I can be of any further help Best Regards Japinder
_________________
 '4 out of Top 5' Instructors on gmatclub  70 point improvement guarantee  www.egmat.com



Intern
Joined: 02 Feb 2011
Posts: 39

Re: Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
08 Dec 2015, 10:58
On the egmat sum option E: Below concept also applies. GCD (A,B) * LCM(A,B) = A * B. Since we already know that GCD(A,B) is A ... implies that LCM(A,B) = B Please anyone confirm my understanding



BSchool Forum Moderator
Joined: 12 Aug 2015
Posts: 2642
GRE 1: 323 Q169 V154

Re: Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
29 Apr 2017, 17:41
Lets male the cases of all options => Option 1 => GCD(3,5)=1 Option 2 => GCD(3,3)=3=> x Option 3 => GCD(3,3)=3=>y Option 4 => GCD(2,1)=>1=>xy Option 5 =>GCD of two numbers can never be greater than either of them. So as x+y is greater than both x and y => It can never be the GCD.
Smash that E.
_________________
MBA Financing: INDIAN PUBLIC BANKS vs PRODIGY FINANCE! Getting into HOLLYWOOD with an MBA! The MOST AFFORDABLE MBA programs!STONECOLD's BRUTAL Mock Tests for GMATQuant(700+)AVERAGE GRE Scores At The Top Business Schools!



Director
Joined: 02 Sep 2016
Posts: 744

Re: Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
17 Aug 2017, 06:45
Bunuel wrote: Lolaergasheva wrote: Which of the following cannot be the GCD of two positive integers x and y? a 1 b x c y d xy e x+y Divisor of a positive integer cannot be more than that integer (for example integer 4 doesn't have a divisor more than 4, the largest divisor it has is 4 itself), so greatest common divisor of two positive integers x and y can not be more than x or y. Answer: E. Bunuel Is this true only for positive integers because a negative integer can have divisors that are greater than the number. For example: 4 has divisors 1, 2, 2, 4, 4, 1 (1, 4) (2,2) (4,1) Is this understanding correct ?



Math Expert
Joined: 02 Sep 2009
Posts: 46090

Re: Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
17 Aug 2017, 06:48
Shiv2016 wrote: Bunuel wrote: Lolaergasheva wrote: Which of the following cannot be the GCD of two positive integers x and y? a 1 b x c y d xy e x+y Divisor of a positive integer cannot be more than that integer (for example integer 4 doesn't have a divisor more than 4, the largest divisor it has is 4 itself), so greatest common divisor of two positive integers x and y can not be more than x or y. Answer: E. Bunuel Is this true only for positive integers because a negative integer can have divisors that are greater than the number. For example: 4 has divisors 1, 2, 2, 4, 4, 1 (1, 4) (2,2) (4,1) Is this understanding correct ? Luckily you don't have to worry about that because every GMAT divisibility will tell you in advance that variables are positive integers only.
_________________
New to the Math Forum? Please read this: Ultimate GMAT Quantitative Megathread  All You Need for Quant  PLEASE READ AND FOLLOW: 12 Rules for Posting!!! Resources: GMAT Math Book  Triangles  Polygons  Coordinate Geometry  Factorials  Circles  Number Theory  Remainders; 8. Overlapping Sets  PDF of Math Book; 10. Remainders  GMAT Prep Software Analysis  SEVEN SAMURAI OF 2012 (BEST DISCUSSIONS)  Tricky questions from previous years.
Collection of Questions: PS: 1. Tough and Tricky questions; 2. Hard questions; 3. Hard questions part 2; 4. Standard deviation; 5. Tough Problem Solving Questions With Solutions; 6. Probability and Combinations Questions With Solutions; 7 Tough and tricky exponents and roots questions; 8 12 Easy Pieces (or not?); 9 Bakers' Dozen; 10 Algebra set. ,11 Mixed Questions, 12 Fresh Meat DS: 1. DS tough questions; 2. DS tough questions part 2; 3. DS tough questions part 3; 4. DS Standard deviation; 5. Inequalities; 6. 700+ GMAT Data Sufficiency Questions With Explanations; 7 Tough and tricky exponents and roots questions; 8 The Discreet Charm of the DS; 9 Devil's Dozen!!!; 10 Number Properties set., 11 New DS set.
What are GMAT Club Tests? Extrahard Quant Tests with Brilliant Analytics



Target Test Prep Representative
Status: Head GMAT Instructor
Affiliations: Target Test Prep
Joined: 04 Mar 2011
Posts: 2570

Re: Which of the following CANNOT be the greatest common divisor [#permalink]
Show Tags
21 Aug 2017, 16:45
Lolaergasheva wrote: Which of the following CANNOT be the greatest common divisor of two positive integers x and y?
A. 1 B. x C. y D. xy E. x+y Since the greatest common divisor or greatest common factor (GCF) of any two positive integers must be no larger than the lesser of the two integers, the GCF can’t be sum of the two integers. That is, the GCF of x and y can’t be x + y. Answer: E
_________________
Jeffery Miller
Head of GMAT Instruction
GMAT Quant SelfStudy Course
500+ lessons 3000+ practice problems 800+ HD solutions




Re: Which of the following CANNOT be the greatest common divisor
[#permalink]
21 Aug 2017, 16:45






