GCF

Question

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
15
45
60
150
300
 B

Please anybody tell how to approach this kind of problems.Indeed i kknow what is GCF and how it was calculated.

gmat1220 · Answer

In "except" question use POE.

The answer will have more or less factors common with 45.

15 = 3 * 5, 45 = 3 * 3 * 5 Common factors = 3 * 5
45 = 3 *3 * 5, 45 = 3 * 3 * 5 Common factors = 3 *3* 5----------> Odd one. hence the answer
60 = 2 * 2 *3 * 5, 45 = 3 * 3 * 5 Common factors = 3* 5
150 = 5 * 3 * 5 * 2, 45 = 3 * 3 * 5 Common factors = 3* 5
300 = 3 * 5 * 2 * 5 * 2, , 45 = 3 * 3 * 5 Common factors = 3* 5

amit2k9 · Answer

K and 45 has GCF = 15
means K = 15,30,60,150,300 ... basically numbers != 45* integer.
Means 15,60,150 and 300 are all possible values of GCF.
Hence B is the answer.

Also,

900 = 2 ^2 * 3^2 * 5 ^2
Let K = 2 ^ a * 3 ^ b * 5 ^c

for 45 as GCF, b= 2 and c= 1 implies that K = 45 * 2^a 
which is not possible, as GCF of K and 45 is 15.

Hence B.

You may use whichever method is suitable for you.

fluke · Answer

GCD is the multiple of lowest power of common prime factors. Now, what does that mean? We'll see using few examples:

GCD(32,64)
32 -> 2^5
64 -> 2^6

Common prime factors: 2
Lower power of 2 in both numbers: 5(in 32) and 6(in 64) so; 5<6
GCD: 2^5

GCD(12,18)
12 -> 2^2*3
18-> 2*3^2

Common factors: 2,3
Lower power of 2: 1(in 18)
Lower power of 3: 1(in 12)
GCD: 2^1*3^1=6

Coming to the question:
GCD(k,45)=15

45-> 3^2*5
GCD=15=3*5. This tells us:
1. There are only two common factors in k and 45 i.e. 3 and 5.
2. The lower power of 5 and 3 in both of k and 45 is 1.

And we know 45 has 2 3's. It means that k has just one 3. If k had two 3's, the GCD(k,45) would be 3^2*5=45. Note that k may have more than one 5's because GCD gives the lesser power of the two; since 45 has just one 5 as its factor, GCD considers only one 5. k may have one or more factors of 5 but it definitely doesn't have more than one 3 in its factor.

So;
GCD(k,900) can not be 45 as 45=3*3*5(Two 3's and one 5). k can't have more than one 3 in its factor.

Ans: "B"

Spidy001 · Answer

My answer is B too.

GCF of K,45 = 15 => K can only have one 3 ,but 5's can be more than 1.

comparing k with given answer choices ,
 we can see the odd one is 45 as that one has more than one 3

GCF

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards