0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

$\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$

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

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)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.