**MGMAT CAT#2**

The greatest common factor of 16 and the positive integer

*n*is 4, and the greatest common factor of

*n*and 45 is 3. Which of the following could be the greatest common factor of

*n*and 210?

3 | ||

14 | ||

30 | ||

42 | ||

70 |

__Solution__

The greatest common factor (GCF) of two integers is the largest integer that divides both of them evenly (i.e. leaving no remainder).

One way to approach the problem is to consider what the GCFs stated in the question stem tell us about

*n*:

The greatest common factor of

*n*and 16 is 4. In other words,

*n*and 16 both are evenly divisible by 4 (i.e., they have the prime factors 2 × 2), but have absolutely no other factors in common. Since 16 = 2 × 2 × 2 × 2,

*n*must have

__exactly__two prime factors of 2--no more, no less.

The greatest common factor of

*n*and 45 is 3. In other words,

*n*and 45 both are evenly divisible by 3, but have absolutely no other factors in common. Since 45 = 3 × 3 × 5,

*n*must have

__exactly__one prime factor of 3--no more, no less. Also,

*n*cannot have 5 as a prime factor.

So,

*n*must include the prime factors 2, 2, and 3. Furthermore, n is not divisible by 8, 9, or 5.

The number 210 has the following prime factorization: 210 = 2 x 3 x 5 x 7. Thus n and 210 are both divisible by 2 and 3, and both might be divisible by 7, but it is not the case that both numbers are divisible by 4 or by 5:

(A) 3: missing a 2

(B) 14: missing a 3

(C) 30: n cannot be divisible by 5

(D) 42: Correct. n and 210 are both divisible by 2 and 3, and n could be divisible by 7.

(E) 70: n cannot be divisible by 5 and must be divisible by 3.

The correct answer is D.

## 1 comment:

16/n , 45/n , 210/n

the three pairs are as above.

Now to find the GCD of a pair of numbers, we do the prime factorisation of each number.

Eg: for 42/140

prime factorisation is as follows:

2x3x7/2x2x5x7

Now pick only the common prime numbers from the two. That will give you GCD:

GCD = 2x7 = 14

OK so now coming back to the question:

Prime factorisation(PF) of the 3 pairs:

PF GCD

1) 2x2x2x2/n 4

2) 3x3x5/n 3

3) 2x3x5x7/n ?

In (1) we can be sure that there are two 2s in n. As the GCD between 16 and n is 4.

Here we can be sure n = 2x2xK ...(some constant K)

In (2) we can be sure that there is one 3 in n and also there is no 5 in n.

Now we are sure that n = 2x2x3xT ...(some constant T)

Now (3) can be re-written as 2x3x5x7/2x2x3xT

So the GCD for sure will have one 2 and one 3 but will surely not have even a single 5.

GCD = 2x3xL ...(some constant L)

Now looking at the options:

1) 3 = 3x1

2) 14 = 2x7

3) 30 = 2x3x5

4) 42 = 2x3x7

5) 70 = 2x5x7

Only 3) and 4) have the 2x3xL structure, but 3) also has a 5.

So 4) is the answer.

Bye ML.

Post a Comment