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$
$\endgroup$
2
-
$\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
Add a comment
|
$\begingroup$
$\endgroup$
7
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$ 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
$\begingroup$
$\endgroup$
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}$$
answered Dec 13 '13 at 22:52
