Help with a proof I came across

Question

I came across this in my textbook and was wondering how it could be proven.

If $a\mid m$ and $b\mid m$ and $gcd(a,m) = 1$, then $ab\mid m$.

It's near some Euclid and Extended Euclid proofs so I was wondering if it had to do with that.

Answer 1

You can use simple properties, such that $ab=gcd(a,b)lcm(a,b)$ so here $ab=lcm(a,b)$. But, by definition of $lcm$, since $a \mid m$ and $b \mid m$ then $lcm(a,b) \mid m$ and thus $ab \mid m$.

You can also use the property that if $a \mid bc$ and $gcd(a,b)=1$ then $a \mid c$. Indeed, you can write $m=kb$ since $b \mid m$, and $a \mid m=kb$ and then apply the property.

I find it also insightful to reason with prime decomposition (here it's rather informal, I should have use p-adic valuation for a real proof) : every positive integer $n \geq 2$ can be decomposed in a unique product of prime numbers.

If $a \mid m$, then prime factors of $a$ (let's say $p_1p_2\ldots p_i$) are in the decomposition of $m$.

Since $b \mid m$, it is also the case for prime factors $p'_1p'_2\ldots p'_j$ of $b$. Finally, $gcd(a,b)=1$ means that $a$ and $b$ have no prime factors in common, so the product $p_1p_2 \ldots p_i p'_1 p'_2 \ldots p'_j$ must appear in the decomposition of $m$, but it's $ab$.

Answer 2

A proof involving Euclidian Algorithm goes as follows: There is a theorem called Bezuts Lemma that follows from E.A. that states that if $(a,b)=1$, then $\exists x,y$ st $ax+by=1$ (take set of numbers of the form, take the smallest one, and use E.A to show both $a,b$ divide it). Then $axc+byc=c$. Let $ak=bc$ then $c=axc+aky=a(xc+ky)$