# Proof that $\gcd$ divides $\operatorname{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\mid m$

• Welcome to Math S.E.! What have you tried so far? Where are you stuck?? – LASV Dec 13 '13 at 22:34
• Thank you! So I was thinking of using the d=ax+by and then multiplying by m but then solving form m but then I have d in the denominator and I think that I want to show that m is a multiple of d not 1/d – Sarah Dec 13 '13 at 22:40

## 2 Answers

The one direction is easy since $\gcd(a,b)\mid a$ and $a\mid \operatorname{lcm}(a,b)$.

For the other direction here is a hint.
Assume that $a\mid b$. What are the $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$?

• if a divides b then the gcd(a,b)=a and the lcm(a,b)=b right? but does that prove it for all cases? – Sarah Dec 13 '13 at 22:48
• That hint is only for the one direction. Do you see which one? – P.. Dec 13 '13 at 22:49
• ya the hint is to go from ii) to i) or am I totally off here? – Sarah Dec 13 '13 at 22:52
• Yes @Sarah you are right! – P.. Dec 13 '13 at 22:52
• ok still stuck I see how it would work if a|b but what if a does not divide b? Them d can still divide m, for example gcd(4,14)=2 and lcm(4,14)=28 and 2 divides 28 but 4 does not divide 14. – Sarah Dec 13 '13 at 23:01

You could also use gcd and lcm in regards to prime decomposition.

Let $a=\prod_{k=1}^{m}p_k^{i_k}, b=\prod_{k=1}^{m}p_k^{j_k}$ where $p_k$ is the $k$'th prime number. Then $$d=\gcd(a,b)=\prod_{k=1}^{m}p_k^{\min\{i_k,j_k\}}$$ $$m=\text{lcm}(a,b)=\prod_{k=1}^{m}p_k^{\max\{i_k,j_k\}}$$ Can you see it from here?

$d|m \Rightarrow m=dx, x \in \mathbb{Z} \Rightarrow \prod_{k=1}^{m}p_k^{\max\{i_k,j_k\}}=\left(\prod_{k=1}^{m}p_k^{\min\{i_k,j_k\}}\right)x.$ Therefore $$x=\frac{\prod_{k=1}^{m}p_k^{\max\{i_k,j_k\}}}{\prod_{k=1}^{m}p_k^{\min\{i_k,j_k\}}}=\prod_{k=1}^{m}p_k^{\max\{i_k,j_k\}-\min\{i_k,j_k\}} \in \mathbb{Z}$$