2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.