Last visit was: 19 Jul 2024, 17:31 It is currently 19 Jul 2024, 17:31
Toolkit
GMAT Club Daily Prep
Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History
Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.

# Which of the following CANNOT be the greatest common divisor of two

SORT BY:
Tags:
Show Tags
Hide Tags
Math Expert
Joined: 02 Sep 2009
Posts: 94421
Own Kudos [?]: 642364 [96]
Given Kudos: 86332
Math Expert
Joined: 02 Sep 2009
Posts: 94421
Own Kudos [?]: 642364 [50]
Given Kudos: 86332
Intern
Joined: 01 Aug 2006
Posts: 18
Own Kudos [?]: 144 [13]
Given Kudos: 0
General Discussion
Manager
Joined: 13 Feb 2012
Posts: 120
Own Kudos [?]: 26 [2]
Given Kudos: 85
Location: Italy
Concentration: General Management, Entrepreneurship
GMAT 1: 560 Q36 V34
GPA: 3.1
WE:Sales (Transportation)
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
2
Kudos
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.
e-GMAT Representative
Joined: 04 Jan 2015
Posts: 3711
Own Kudos [?]: 17337 [3]
Given Kudos: 165
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
1
Kudos
2
Bookmarks
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 even-odd nature
(D) All the factors of B are divisible by A
(E) The LCM of A and B is B

Will post the solution in this thread on May 1, 2015. Till then, happy solving!

Regards
Japinder
e-GMAT Representative
Joined: 04 Jan 2015
Posts: 3711
Own Kudos [?]: 17337 [6]
Given Kudos: 165
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
2
Kudos
4
Bookmarks
EgmatQuantExpert wrote:
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 even-odd nature
(D) All the factors of B are divisible by A
(E) The LCM of A and B is B

Will 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 number
Consider 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 even-odd nature
Consider A = 3 and B = 6. Here too, GCD(A,B) = A but the even-odd 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 B
We 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
Manager
Joined: 29 Mar 2015
Posts: 69
Own Kudos [?]: 45 [0]
Given Kudos: 21
Concentration: Strategy, Operations
GMAT 1: 700 Q51 V33
WE:Research (Other)
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
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)?
e-GMAT Representative
Joined: 04 Jan 2015
Posts: 3711
Own Kudos [?]: 17337 [0]
Given Kudos: 165
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
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 nailgmat2015

Thank you for your questions. PFB my response.

1. This question is of GMAT 650- difficulty level. That said, I don't think the difficulty-level 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 step-by-step 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 Even-Odd numbers, Prime Numbers and LCM-GCD. And, you'll see for yourself how even the most difficult Number Properties questions can be solved by applying, in a step-by-step 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
Director
Joined: 02 Sep 2016
Posts: 525
Own Kudos [?]: 195 [0]
Given Kudos: 277
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
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 x-y
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.

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: 94421
Own Kudos [?]: 642364 [0]
Given Kudos: 86332
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
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 x-y
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.

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.
Target Test Prep Representative
Joined: 04 Mar 2011
Affiliations: Target Test Prep
Posts: 3036
Own Kudos [?]: 6595 [3]
Given Kudos: 1646
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
2
Kudos
1
Bookmarks
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. x-y
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.

Manager
Joined: 29 May 2016
Posts: 102
Own Kudos [?]: 141 [1]
Given Kudos: 178
Location: Czech Republic
Concentration: Finance, Strategy
GMAT 1: 700 Q47 V38
GPA: 3.94
WE:Corporate Finance (Investment Banking)
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
1
Kudos
If I assume that x=y, wouldn't that make answer choice (D) nonsensical?

In other words if x=y then if x=2 2-2=0. But can zero be the greatest common divisor of positive integers?
CEO
Joined: 07 Mar 2019
Posts: 2621
Own Kudos [?]: 1869 [0]
Given Kudos: 763
Location: India
WE:Sales (Energy and Utilities)
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
Xin_Cho wrote:
If I assume that x=y, wouldn't that make answer choice (D) nonsensical?

In other words if x=y then if x=2 2-2=0. But can zero be the greatest common divisor of positive integers?

Xin Cho

You have grabbed the question at its weakest point.
Perhaps that's why it didn't feature in latest OGs.
But question is not that all the options would be applicable to one set of example.
The options are applicable to various cases not a single one.

Anyway nice observation.
GMAT Club Legend
Joined: 12 Sep 2015
Posts: 6804
Own Kudos [?]: 30837 [1]
Given Kudos: 799
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
1
Bookmarks
Top Contributor
Bunuel 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) x - y
(E) x + y

Key concept: Each divisor of integer N is less than or equal to N
For example, here are the divisors of 15: {1, 3, 5, 15}
Notice that every divisor is less than or equal to 15.

Similarly, if a number is a divisor of both x AND y, then that number must be less than or equal to x AND less than or equal to y.
As such, the greatest common divisor of x and y cannot be greater than both x and y
Since (x + y) > x and (x + y) > y, we can conclude that x+y cannot be the greatest common divisor of x and y.

Cheers,
Brent
Tutor
Joined: 05 Apr 2011
Status:Tutor - BrushMyQuant
Posts: 1801
Own Kudos [?]: 2143 [1]
Given Kudos: 100
Location: India
Concentration: Finance, Marketing
Schools: XLRI (A)
GMAT 1: 700 Q51 V31
GPA: 3
WE:Information Technology (Computer Software)
Which of the following CANNOT be the greatest common divisor of two [#permalink]
1
Bookmarks
Top Contributor
Theory

➡ GCD of two numbers is always smaller than or equal to the smaller of those two numbers
➡ GCD (a,b) <= Smaller (a,b)

Which of the following CANNOT be the greatest common divisor of two positive integers x and y

Let's take each option choice and evaluate

(A) 1
Now, we can take co-prime values of x and y (co-primes are numbers which have only 1 as as the common factor) and this will be true.
Ex, x=2 and y=3 => GCD = 1
=> TRUE

(B) x
This can be true when one number is x and other number is a multiple of x
Example: One number is 2 (which is x) and other number is 2*2 = 4 (which is a multiple of x). Making the GCD = 2 (which is x)
=> TRUE

(C) y
This can be true when one number is y and other number is a multiple of y
Example: One number is 2 (which is y) and other number is 2*2 = 4 (which is a multiple of y). Making the GCD = 2 (which is y)
=> TRUE

(D) x - y
Take x = 4, y = 2.
x - y = 4-2 = 2
GCD (4,2) = 2
=> TRUE

(E) x + y
Now, GCD of two numbers is always smaller than or equal to the smaller of those two numbers
=> GCD(x,y) <= Smaller of x and y
So, GCD can never be x+y as x+y will be greater than both x and y.
=> FALSE

So, Answer will be E
Hope it helps!

To learn more about LCM and GCD watch the following videos

Non-Human User
Joined: 09 Sep 2013
Posts: 34034
Own Kudos [?]: 853 [0]
Given Kudos: 0
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
Re: Which of the following CANNOT be the greatest common divisor of two [#permalink]
Moderator:
Math Expert
94421 posts