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$

  • $\begingroup$ Welcome to Math S.E.! What have you tried so far? Where are you stuck?? $\endgroup$ – LASV Dec 13 '13 at 22:34
  • $\begingroup$ 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 $\endgroup$ – Sarah Dec 13 '13 at 22:40

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

  • $\begingroup$ 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? $\endgroup$ – Sarah Dec 13 '13 at 22:48
  • $\begingroup$ That hint is only for the one direction. Do you see which one? $\endgroup$ – P.. Dec 13 '13 at 22:49
  • $\begingroup$ ya the hint is to go from ii) to i) or am I totally off here? $\endgroup$ – Sarah Dec 13 '13 at 22:52
  • $\begingroup$ Yes @Sarah you are right! $\endgroup$ – P.. Dec 13 '13 at 22:52
  • $\begingroup$ 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. $\endgroup$ – 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}$$


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.