Advanced Quant - Workout set 2 - #12

[RaffaeleM39]

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]

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]

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.