# GCD divisibility of LCM

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

• It should be $m=dq$ for some $q$. To prove the other direction, let $a=dq$, $b=d$. – user236182 Apr 21 '16 at 16:45
• 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$. – Batominovski Apr 21 '16 at 17:13

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.

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