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 Answers 2

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
    Commented Jan 27, 2021 at 10:46
  • $\begingroup$ I edited to include every explanation $\endgroup$
    – user799688
    Commented Jan 27, 2021 at 11:00
  • 1
    $\begingroup$ $m=21$ , $n=27$ with $d=3$ and $m=48$ , $n=54$ with $d=6$ $\endgroup$
    – Lozenges
    Commented Jan 27, 2021 at 11:01
  • $\begingroup$ $d$ cannot be $2$ since $3$ has to divide $m+6$ and $n$ and therefore $3$ divides $d$ $\endgroup$
    – Lozenges
    Commented Jan 27, 2021 at 11:19
  • $\begingroup$ In above answer he said d can be 2 also. $\endgroup$
    – Asim
    Commented Jan 27, 2021 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .