Prove that if $\gcd(a,b)=1$ and $a|mb$ then $a|m$.

Question

I've tried out a few pairs of numbers for $a$,$b$ where I have combinations of prime-prime, prime-non prime, non-prime-non-prime, and I know the statement is true, but how should I go about proving this?

I know that if $\gcd(a,b)=1$ and $a|mb$, then $m=a$, $m=2a$, $m=3a$ etc. Does this then prove that $a|m$?

Answer 1

Bezout's lemma is a good place to start. Since ${\rm gcd}(a,b) = 1$ there exist integers $x$ and $y$ such that $ax + by = 1$.

Because $a | mb$ there exists an integer $t$ such that $at = mb$. Multiply the first equation by $m$

$$amx + bmy = m$$

then use $at = mb$

$$amx + aty = m$$

and finally factor out $a$

$$a(mx + ty) = m$$

to discover $a|m$.

Answer 2

If the $\gcd(a,b)=1$ then there exist $x,y$ s.t $$ax+by=1$$ and so if we multiply both sides by $m$ we get $$amx+bmy=m$$
LHS is divisible by $a$ and so RHS.