Advanced Applications of Common Factors on the GMAT – Part II

Quarter Wit, Quarter WisdomThere is something about factors and divisibility that people find hard to wrap their heads around. Every advanced application of a basic concept knocks people out of their seats! Needless to say, that the topic is quite important so we are trying to cover the ground for you. Here is another post on the topic discussing another important concept.

In a previous post, we saw that

“Two consecutive integers can have only 1 common factor and that is 1.”

This implies that N and N+1 have no common factor other than 1. (N is an integer)

Similarly,

N + 5 and N + 6 have no common factor other than 1. (N is an integer)

N – 3 and N – 2 have no common factor other than 1. (N is an integer)

2N and 2N + 1 have no common factor other than 1. (N is an integer)

We are sure you have no problem up until now.

How about:

N and 2N+1 have no common factor other than 1. (N is an integer)

It is a simple application of the same concept but makes for a 700 level question!

2N and 2N+1 have no common factor other than 1 – we know

The factors of N will be a subset of the factors of 2N. It will not have any factors which are not there in the list of factors of 2N. So if 2N and another number have no common factors other than 1, N and the same other number can certainly not have any common factor other than 1.

Taking an example, say N = 6

Factors of 2N (which is 12) are 1, 2, 3, 4, 6, 12.

Factors of 2N + 1 (which is 13) are 1, 13.

2N and 2N + 1 can have no common factors.

Now think, what are the factors of N? They are 1, 2, 3, 6 (a subset of the factors of 2N)

They will obviously not have any factor in common with 2N+1 (except 1) since these are the same factors as those of 2N except that these are fewer.

So we can deduce the following (N and M are integers):

M and NM +1 will have no common factor other than 1.

8 and 8M + 1 will have no common factor other than 1.

M and NM – 1 will have no common factor other than 1.

and so on…

Here is the 700 level official question of this concept:

Question: If x and y are positive integers such that x = 8y + 12, what is the greatest common divisor of x and y?

Statement 1: x = 12u, where u is an integer.

Statement 2: y = 12z, where z is an integer.

Solution:

x = 8y + 12

We need to find the greatest common divisor of x and y. We have 8y in the equation. A couple of immediate deductions:

The factors of y will be a subset of the factors of 8y.

The difference between x and 8y is 12 so the greatest common divisor of x and 8y will be a factor of 12 (discussed in this post a few weeks back).

This implies that the greatest factor that x and y can have must be a factor of 12.

Looking at the statements now:

Statement 1: x = 12u, where u is an integer.

Now we know that x has 12 as a factor. The problem is that we don’t know whether y has 12 as a factor.

y could be 3 —> x = 8*3 + 12 = 36 (a multiple of 12). Here greatest common divisor of x and y will be 3.

or y could be 12 —> x = 8*12 + 12 = 108 (a multiple 12). Here greatest common divisor of x and y will be 12.

So this statement alone is not sufficient.

Statement 2: y = 12z, where z is an integer.

This statement tells us that y also has 12 as a factor. So now do we just mark (C) as the answer and move on? Well no! It seems like an easy (C) now, doesn’t it? We must analyse this statement alone.

Substituting y = 12z in the given equation:

x = 8*12z + 12

x = 12*(8z + 1)

So this already gives us that x has 12 as a factor. We don’t really need statement 1.

Since both x and y have 12 as a factor and the highest common factor they can have is 12, greatest common divisor of x and y must be 12.

This statement alone is sufficient to find the greatest common divisor of x and y.

Answer (B)

Karishma, a Computer Engineer with a keen interest in alternative Mathematical approaches, has mentored students in the continents of Asia, Europe and North America. She teaches the GMAT for Veritas Prep and regularly participates in content development projects such as this blog!