If k is a positive integer and the greatest common divisor of k and 45 is 15, then the greatest common divisor of k and 900 may be any of the following EXCEPT
(A) 15
(B) 45
(C) 60
(D) 150
(E) 300
Multiples and factors
This topic has expert replies
GMAT/MBA Expert
- [email protected]
- Elite Legendary Member
- Posts: 10392
- Joined: Sun Jun 23, 2013 6:38 pm
- Location: Palo Alto, CA
- Thanked: 2867 times
- Followed by:511 members
- GMAT Score:800
Hi ikaplan,
This question is ultimately about "prime factorization" (the idea that a positive integer is either prime or can be "broken down" into the product of a bunch of primes).
We're told that the greatest common divisor of K and 45 is 15.
Since 45 = (3)(3)(5)
and 15 = (3)(5)
then K, at the minimum is (3)(5). It might have OTHER prime factors as well, BUT it can't have another 3. Here's why...
If K = (2)(3)(5) = 30, then the greatest common divisor of 30 and 45 is 15, so the above statement holds true.
If K = (3)(3)(5) = 45, then the greatest common divisor of 45 and 45 is 45, and the above statement doesn't make sense.
We're asked which of the following could be the greatest common divisor of K and 900 EXCEPT....
900 = (3)(3)(2)(2)(5)(5)
K = (3)(5)(possibly some other primes other than 3)
We can now use the answer choices to eliminate the possibilities:
A = 15 = (3)(5) is POSSIBLE
B = 45 = (3)(3)(5) is NOT POSSIBLE
C = 60 = (3)(5)(2)(2) is POSSIBLE
D = 150 = (3)(5)(2)(5) is POSSIBLE
E = 300 = (3)(5)(2)(2)(5) is POSSIBLE
Final Answer: B
GMAT assassins aren't born, they're made,
Rich
This question is ultimately about "prime factorization" (the idea that a positive integer is either prime or can be "broken down" into the product of a bunch of primes).
We're told that the greatest common divisor of K and 45 is 15.
Since 45 = (3)(3)(5)
and 15 = (3)(5)
then K, at the minimum is (3)(5). It might have OTHER prime factors as well, BUT it can't have another 3. Here's why...
If K = (2)(3)(5) = 30, then the greatest common divisor of 30 and 45 is 15, so the above statement holds true.
If K = (3)(3)(5) = 45, then the greatest common divisor of 45 and 45 is 45, and the above statement doesn't make sense.
We're asked which of the following could be the greatest common divisor of K and 900 EXCEPT....
900 = (3)(3)(2)(2)(5)(5)
K = (3)(5)(possibly some other primes other than 3)
We can now use the answer choices to eliminate the possibilities:
A = 15 = (3)(5) is POSSIBLE
B = 45 = (3)(3)(5) is NOT POSSIBLE
C = 60 = (3)(5)(2)(2) is POSSIBLE
D = 150 = (3)(5)(2)(5) is POSSIBLE
E = 300 = (3)(5)(2)(2)(5) is POSSIBLE
Final Answer: B
GMAT assassins aren't born, they're made,
Rich
- theCodeToGMAT
- Legendary Member
- Posts: 1556
- Joined: Tue Aug 14, 2012 11:18 pm
- Thanked: 448 times
- Followed by:34 members
- GMAT Score:650
k = +ve
GCD = 15 = 5x3
that means 5x3 is common between k & 45
k = 5 x 3 x Y
45 = 5 x 3 x 3
THis implies that K cannot have another "3" or else GCD should have been 45
So, [spoiler]{B}[/spoiler]
GCD = 15 = 5x3
that means 5x3 is common between k & 45
k = 5 x 3 x Y
45 = 5 x 3 x 3
THis implies that K cannot have another "3" or else GCD should have been 45
So, [spoiler]{B}[/spoiler]
R A H U L
- 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
Since the greatest integer that divides into both k and 45 is 15, k cannot be a multiple of 45.ikaplan wrote:If k is a positive integer and the greatest common divisor of k and 45 is 15, then the greatest common divisor of k and 900 may be any of the following EXCEPT
(A) 15
(B) 45
(C) 60
(D) 150
(E) 300
To illustrate:
If k=90 -- a multiple of 45 -- then the GCF of k=90 and 45 would be 45, not 15.
Since k cannot be divisible by 45, the GCF of k and 900 cannot be divisible by 45.
Thus, the GCF of k and 900 cannot be answer choice B.
The correct answer is B.
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