## Advanced Quant - Workout set 2 - #12

If you're experiencing a roadblock with one of the Manhattan Prep GMAT math strategy guides, help is here!
RaffaeleM39
Students

Posts: 33
Joined: Fri Aug 21, 2015 1:57 am

### Advanced Quant - Workout set 2 - #12

m = 4n + 9, where n is a positive integer. What is the greatest common factor of m and n?

(1) m=9s, where s is a positive integer
(2) n?=4t, where t is a positive integer

In the solution discussing point (1): if (1) is true, then n itself must be a multiple of 9. I have understood that.
What I did not understand is the next sentence: "If both m and n are multiples of 9, and m is exactly 9 units away from 4n, then the largest possible common factor is 9". Can you prove that besides listing cases?

I can't get toward a proof or I can get the intuition behind this.
RaffaeleM39
Students

Posts: 33
Joined: Fri Aug 21, 2015 1:57 am

### Re: Advanced Quant - Workout set 2 - #12

RaffaeleM39 wrote:
m = 4n + 9, where n is a positive integer. What is the greatest common factor of m and n?

(1) m=9s, where s is a positive integer
(2) n?=4t, where t is a positive integer

In the solution discussing point (1): if (1) is true, then n itself must be a multiple of 9. I have understood that.
What I did not understand is the next sentence: "If both m and n are multiples of 9, and m is exactly 9 units away from 4n, then the largest possible common factor is 9". Can you prove that besides listing cases?

I can't get toward a proof or I can get the intuition behind this.

I was able to prove it

n = 9*k'

m = 4n + 9 = 4*9*k'+9=9(4k'+1)

GCD(m,n) = GCD(4*9*k'+9, 9*k') = GCD(4*9*k'+9 - 9*k', 9*k') = GCD(3*9*k'+9, 9*k')

And you can continue until ending up with
GCD(9, 9*k') = 9 for every k'
Sage Pearce-Higgins
ManhattanGMAT Staff

Posts: 943
Joined: Thu Apr 03, 2014 4:04 am

### Re: Advanced Quant - Workout set 2 - #12

It seems you have things under control! As much as your proof is a good brain workout and improves your insight as part of the review process, I would encourage you to get familiar with picking examples as a way to understand things quickly in a test situation.