Proof that if $\gcd(a,b) = 1$ and $a\mid n$ and $b\mid n$, $ab \mid n$

Question

I'm learning about properties of greatest common divisors, specifically when two numbers are relatively prime.

The exercise I'm working through is :

Suppose that $\gcd(a,b) = 1$ and that $a\mid n$ and $b\mid n$. Prove that $ab\mid n$

Proof(so far):

$\gcd(a,b)=1$ implies $am+bk = 1$ for some integers $m$ and $k$.

(Given hint) Multiplying the equation by $n$ yields: $$amn+bkn=n$$

I'm not sure what to do after applying the hint. Am I supposed to show that $ab$ divides both $amn$ and $bkn$?

Thanks in advance.

Answer 1

Yes, from there you know that if $(an)m+(bn)k=n$ for some $m$ and $k$, then since $b\mid n$, $ab|an$, and likewise since $a\mid n$, $ab\mid bn$.

Thus there exist $x$ and $y$ such that: $$(an)m+(bn)k=(abx)m+(aby)k=(ab)(xm+yk)=n\implies ab\mid n$$

Answer 2

You are supposed to show that $ab$ divides $n$. That means you are supposed to show that $\frac n{ab}$ is an integer. So the next step is to divide $n$ by $ab$, and then show that the result is an integer: $$\frac n{ab}=\frac{amn+bkn}{ab}=\frac{amn}{ab}+\frac{bkn}{ab}=\frac{mn}b+\frac{kn}a=m\frac nb+k\frac na$$ and now use the fact that $\frac na,\frac nb,m,k$ are all integers.

Answer 3

Just a remark that you don't need to use the hint, or Bézout coefficients at all, as long as you know that the least common multiple $m$ of any pair of numbers $a,b$ divides all common multiples of $a,b$. [The remainder of the common multiple by $m$ is a common multiple less then $m$, hence zero.] Therefore in the concrete situation $m$ divides the common multiple $ab$, but in fact $m=ab$ since otherwise $\frac{ab}m$ is a common divisor of $a,b$ that is$~{}>1=\gcd(a,b)$, a contradiction. But now the least common multiple $ab$ divides the common multiple $n$ of $a,b$.