# Is this a valid proof of divisibility by product of coprimes?

Premise: $m \mid a$

Premise: $n \mid a$

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

Show: $mn \mid a$

?Proof:

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

• Looks good (and elegant) to me. – 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$$
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$$