If p and q are positive integers such that p = 4q – 3....

If p and q are positive integers such that p = 4q – 3, what is the greatest common divisor of p and q?
(1) q = 3k, where k is an integer
(2) p = 3m, where m is an integer

1) p = 12k -3,or, p= 3 (4k -1) and q= 3k. The GCM is 3. e.g: for k =1, p=9, q= 3. Again when k =2, p= 21, q=6. Sufficient.
2) p = 4q -3, and p =3m, So, 3m +3 = 4q or, q= 3/4 (m+1), p= 3m .
Lets saay, m = 1, p =3, q= 3/2. GCM is 1. Again m =2, p =6, q =9/4, GCM is 1. When m= 3, p is 9 and q is 3, then GCM is 3. Insufficient.
A is the answer.

If p and q are positive integers such that p = 4q – 3, what is the greatest common divisor of p and q?

(1) q = 3k, where k is an integer
(2) p = 3m, where m is an integer

p = 4q - 3 and p and q are positive integers

What is GCF => lowest power in prime factorization that p and q shares

i) q=3k => p=12k - 3 => p = 3(4k-1)

As we see p and q shares 3^1 in them. Let's analyze (k) and (4k-1)

k = 1, 4k-1 = 3; k=2, 4k-1 = 9; k=3, 4k-1 = 11

(k) and (4k-1) will never share a common factor for any integer k.

Thus GCF will always be 3. - Sufficient

ii) p = 3m => 3m = 4q - 3
4q = 3(m+1)

in this, m has to be odd such that it is a multiple of 4 for q to be an integer.

possible values of m = 3, 7, 11, 15 (a form of 4k-1)... => q=3, 6, 9, 12 (a multiple of 3) ... and p = 9, 21, 33, 45 ....

Again, the GCF between p and q will always be 3 - Sufficient

Answer - D

If p and q are positive integers such that p = 4q – 3, what is the greatest common divisor of p and q?
(1) q = 3k, where k is an integer
(2) p = 3m, where m is an integer

ANS D

STatement 1 :
q = 3k ----> p = 12k-3 ------> p = 3(4k-1) -------- GCD OF k and 4k-1 will be 1 ------> GCD of 3k and 3(4k-1) will be 3x1 SUFF

STATEMENT 2:

p=3m ---- 4q = 3(m+1) If q is +ve integer than m+1 = 4l -------> GCD of (p,q) = GCD(3m , 3 * (4l/4)) = GCD( 3m , 3l ) = 3 GCD ( m , l ) = 3 GCD ( m , (m+1)/4 ) = 3 ..... SUFF

Ans: D

p = 4q – 3
1) q = 3k, where k is an integer
p=4.3k-3=3(4k-1)
gcd(p,q)=gcd(3(4k-1),3k)=3(I have also checked with putting values for k=1,2,3 etc k not=0,as p,q are +ve int)
so,1 is suff

2) p = 3m, where m is an integer
p = 4q – 3
q=(3(m+1))/4
gcd(p,q)=gcd(3m,(3(m+1))/4)=3(I have also checked with putting values for m=1,2,3 etc m not=0,as p,q are +ve int)

so, 2 is suff

Hey minustark,


Thanks for posting your response.

There's a small mistake in your analysis of the second statement.

Notice that in the question stem, it is clearly stated that p and q are "positive integers". Thus, you cannot consider q as \(\frac{3}{2}\) or \(\frac{9}{4}\).

After getting \(q =\frac{ 3(m+1)}{4}\), you should have inferred that m + 1 must be a multiple of 4, if we want q to be an integer. Also, you should have inferred that m + 1 in q and m in p will be co-prime.

Thus, the only factor that is common between p and q will be then 3. Hence, the GCD must be 3.

Here's the official solution of this question.

We are given that,

p >0, q>0
p = 4q-3

Need to find, GCD(p,q).

1. q = 3k
So, p = 4.3k-3 = 3(4k-1)

Here, when k = odd, (4k-1) will be even. When k = 3, (4k-1) will be '1' less than the multiple of '3'. Hence k and (4k-1) will never have anything in common.

So, GCD(p,q) = 3

2. p = 3m
So, q = (3m+3)/4 = 3/4(m+1)

Here (m+1) has to be multiple of 4 as q is integer. So, m+1 = 4k, m=4k-1

p= 3(4k-1)
q= 3k
These are the same equations as in the choice 1.

So, GCD(p,q) = 3

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.