# Coprime Proof

• Nov 5th 2009, 05:05 AM
sirellwood
Coprime Proof
Hi all,

a, b are coprime integers such that a|m and b|m, for some integer m. Prove, using Euclid’s lemma, that ab|m.
• Nov 6th 2009, 05:58 AM
courteous
$a|m \Rightarrow m=xa$
$b|m \Rightarrow m=yb$
$ab|m \Rightarrow m=z(ab)=z(\frac{m}{x}\frac{m}{y})=mz(\frac{1}{x}\f rac{1}{y})$

This probably doesn't suffice, you'd might want to wait for a reply from one of the forum's masters.(Wink) (Waiting for their admonishment.)

Meanwhile, is there a [tex] tag keyboard shortcut?
• Nov 6th 2009, 06:05 AM
Media_Man
Consider: $a|m$, so $m=xa$ for some $x$. Since $b|m$, $b|xa$. Since $a,b$ are coprime, $b\not|a$, nor do they share any factors whatsoever, therefore $b|x$, and $x=yb$ for some $y$. Now $m=xa=yab$, so $ab|m$. QED

• Nov 6th 2009, 08:47 AM
Drexel28
Quote:

Originally Posted by sirellwood
Hi all,

a, b are coprime integers such that a|m and b|m, for some integer m. Prove, using Euclid’s lemma, that ab|m.

Alternatively

Problem: Suppose $\text{gcd}\left(a,b\right)=1$. Furthermore suppose that $a\mid m$ and $b\mid m$. Prove that $ab\mid m$.

Proof: Since $\text{gcd}(a,b)=1$ we know $\exists x,y\in\mathbb{Z}$ such that $ax+by=1$. Therefore for the same $x,y$ we'd have that $axm+bmy=m$. Since $b|m$ it is clear that $ab|axm$ similarly since $a|m$ is it clear that $ab|bym$. Therefore $ab|axm+bym=m\quad\blacksquare$