GCD

knight247 wrote:m=4n+9, where n is a positive integer. What is the GCD of m and n?
(1)m=9s, where s is a positive integer
(2)n=4t, where t is a positive integer

OA is A

What we know is that m is an odd positive integer.

I. If m = 9s, where s is a positive integer, then n is also a multiple of 9 otherwise 9s cannot be equal to 4 n + 9, thus we can trust that n = ¼ (9s - 9) or n = (9/4) (s – 1). So we can further realize that s – 1 is divisible by 4 or at minimum, s is odd and it may or may not be a multiple of 9 but it surely is not a multiple of 4. Now, to find the GCD of m and n all we need to decide is what is the GCD of s and ¼ (s – 1) where s could be 5, 9, 13, etceteras or hence ¼ (s – 1) could be 1, 2, 3, etceteras respectively. See, all such pairs (5, 1), (9, 2), (13, 1) etceteras contain two co primes with GCD 1. Hence, the GCD of 9s and (9/4) (s – 1) is 9, or the GCD of m and n is 9. To believe this, we can have another point of view, let’s take ¼ (s – 1) = k, so that s = 4 k + 1 and k and 4 k + 1 cannot have a prime in common.


Remaining of the post tomorrow as I am in hurry...