# Need Greatest common divisor explaination

In the book the problem says: What is the GCD of two natural numbers m and n if after increasing the number m by 6 the GCD of two numbers increased 9 times.

And the solution it gives is 2,3 or 6. Can someone explain how is it. And what values of m and n satisfy the equation. I can't find any. May be i couldn't understand the question or the book is miss printed. Idk. Please help me understand this with some examples. Thanks

$$\gcd(a;b)=d$$ and $$\gcd(a;b+6)=9d$$ so $$d\mid b+6\mbox{ and }d\mid b\Rightarrow d\mid 6$$

Assume $$d=1$$. Then $$a$$ and $$b$$ are coprime and $$a=9x$$ and $$b+6=9y$$ with coprime $$x,y$$. This implies $$3\mid a$$ and $$3\mid b$$ so contradiction.

So $$d\mid 6$$ and $$d\neq 1$$, so $$d$$ can only be $$2,3$$ or $$6$$

• Can u give me one example of m, n and d values where this equation is true
– Asim
Jan 27 at 10:46
• I edited to include every explanation
– user799688
Jan 27 at 11:00
• $m=21$ , $n=27$ with $d=3$ and $m=48$ , $n=54$ with $d=6$ Jan 27 at 11:01
• $d$ cannot be $2$ since $3$ has to divide $m+6$ and $n$ and therefore $3$ divides $d$ Jan 27 at 11:19
• In above answer he said d can be 2 also.
– Asim
Jan 27 at 12:32

Hint $$\,$$ By below, with $$\,j=2,\, k = 3\,\Rightarrow\, 3\mid (m,n)\mid 6$$

Lemma $$\, \ k,(m,n)\mid (m,\:\!n\!+\!jk)\!\iff\! k\mid (m,n)\mid jk$$

Proof $$\,\$$ Note $$\ (m,n)\mid n,\,n\!+\!jk\,\iff (m,n)\mid jk,\,$$

and $$\ k\mid m,n\!+\!jk\! \iff k\mid m,n\iff k\mid (m,n)$$