0
$\begingroup$

Show that the following conditions are equivalent:

i) There exist positive integers $a,b$ such that $\gcd(a,b)=d$ and $\operatorname{lcm}(a,b)=m$.

ii) $d∣m$

The first direction is very straightforward but for the second direction we start with so little I wrote $d = mq$ for some $q$ in the integers but I'm confused as to where to go next

$\endgroup$
  • 1
    $\begingroup$ It should be $m=dq$ for some $q$. To prove the other direction, let $a=dq$, $b=d$. $\endgroup$ – user236182 Apr 21 '16 at 16:45
  • 1
    $\begingroup$ A much more interesting (but not difficult) question is the following. Given positive integers $d$ and $m$, how many pairs $(a,b)$ of positive integers are there such that $\gcd(a,b)=d$ and $\text{lcm}(a,b)=m$. $\endgroup$ – Batominovski Apr 21 '16 at 17:13
1
$\begingroup$

If you have $d|m$, you immediately get $gcd(d,m)=d$ and $lcm(d,m)=m$, so the pair $(d/m)$ does the job completing the proof of the other direction.

$\endgroup$
0
$\begingroup$

We know that $$\gcd(a,b) | ax + by$$ So, the GCD divides any linear combination of $a$ and $b$. Isn't the LCM a linear combination of $a$ and $b$? $LCM = ka + 0\cdot b$ for some $k$.

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