Premise: $m \mid a$

Premise: $n \mid a$

Premise: $\gcd(m,n)=1$

Show: $mn \mid a$


$m \mid a \Rightarrow mn \mid an$

$n \mid a \Rightarrow mn \mid am$

$mn \mid am \wedge mn \mid an \Rightarrow mn \mid (ams + ant) \Rightarrow mn \mid a(ms+nt) \; \forall s, t \in \mathbb{z}$

By Bezout's lemma, $\exists x, y \in \mathbb{Z}$ such that $mx+ny=1$.

Assume we have the solution for $(x, y)$.

Then substituting into above, $ mn \mid a(mx+ny) \Rightarrow mn \mid a \cdot 1 \Rightarrow mn \mid a$

Is there a flaw in this?

  • $\begingroup$ Looks good (and elegant) to me. $\endgroup$ – Guest Jun 6 '17 at 3:13

That looks good. One note that is likely a typo, but it should be $n$ instead of $b$ when you introduce the part involving Bezout's Lemma.

Here is an alternative solution: By Bezout's Lemma $\gcd(m,n)=1\iff\exists u,v\in\Bbb Z:mu+nv=1$, and $m\mid a\,\land\,n\mid a\iff\exists c,d\in\Bbb Z:a=mc=nd$. Hence, we have $$mu+nv=1\Rightarrow mua+nva=a\Rightarrow mund+nvmc=a\Rightarrow mn(ud+vc)=a\Rightarrow mn\mid a$$

These solutions are similar, as they use some facts about divisibility, and of course use Bezout's Lemma.

  • $\begingroup$ indeed those were typos you pointed out, which I have corrected $\endgroup$ – doctorjay Jun 6 '17 at 11:48

It is coreect - a standard Bezout-based proof. If we replace Bezout by gcd laws and do it bidirectionally we obtain a more general proof that $\,{\rm lcm}(m,n) = mn/\gcd(m,n),\,$ viz.

$$ m,n\mid a\iff mn\mid an,am\iff mn\mid(an,am) = a(n,m)\iff mn/(n,m)\mid a$$


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.