For $a \in\Bbb N$, $b\in\Bbb N$, $μ \in\Bbb N^*$, we have $μ = \operatorname{lcm}(a,b) \iff μ = αa\text{ and }μ= βb$ and $\gcd(α,β)$ is $1$

Till now I succeeded to prove the left $\Rightarrow$ right implication, now I need to prove the reciprocal ($\Leftarrow$ way)

Here is my work: http://imgur.com/a/oPy6XDN

Can someone help me, or give me a hint? Rules : you can't use the expression ($a \wedge b)(a\vee b)=ab$, $(ka)\vee(vkb) = k(a\vee b)$ + You can also help me improve my redaction if possible..


This answer proves the theorem below using basic divisibility laws (with a duality viewpoint).

Theorem $\ $ If $\,\ a,b\mid m\,\ $ then $\ \displaystyle \frac{m}{{\rm lcm}(a,b)} \,=\,\gcd\left(\frac{m}a,\frac{m}b\right),\ $ i.e. $\ {\rm lcm}(a,b)' = \gcd(a',b')$

$\begin{align}{\rm We\ seek}\ \ m = {\rm lcm}(a,b) &\iff a,b\mid m\ \ \&\ \gcd\left(\dfrac{m}a,\dfrac{m}b\right) = 1,\ \ \text{which by the above is}\\[.3em] &\iff a,b\mid m\ \ \&\ \ \dfrac{m}{{\rm lcm}(a,b)}\, =\, 1,\quad\ \ \ \text{which is clearly true.} \end{align}$

Remark $ $ The linked proof using cofactor duality reveals your equivalence boils down to

${\rm lcm}(a,b) = m \iff {\rm lcm}(a,b)' = m',\ $ via $\ {\rm lcm}(a,b)' = \gcd(a',b') = \gcd(m/a,m/b)$

Alternatively $ $ we show: $ $ a common multiple $m$ of $\,a,b\,$ is least $\iff \gcd(m/a,m/b)=1$

Proof $\ $ If the gcd $= c> 1\,$ then $\,c\mid m/a,m/b\,$ so $\,a,b\mid m/c,\,$ therefore $m$ is not least. $ $ Conversely, if $m$ is not least then $\,m = c\ell\,$ for $\,\ell\,$ least, so the gcd $= (c\ell/a,c\ell/b) = c(\ell/a,\ell/b) > 1\,$ by $\,c>1$.

  • $\begingroup$ The problem is that my teacher won't accept this as a proof since he told us to prove it only by using divisibility laws and gcf laws, and I'm not allowed to use that expression even if it's derived as a corollary... + One more thing I'm not allowed to use fractions : notice how I didn't use any in my paper. I hope you understand, thanks. $\endgroup$ – Mrkinix May 24 at 0:47
  • $\begingroup$ @Mrkinix Again, the linked proof uses only simple divisibility laws and the definition of gcd and lcm. You can ignore the Corollary since I don't use it above. $\endgroup$ – Bill Dubuque May 24 at 0:50
  • $\begingroup$ @Mrkinix I added an alternative proof. $\endgroup$ – Bill Dubuque May 24 at 2:18

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.