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.

Printable View

- Nov 5th 2009, 05:05 AMsirellwoodCoprime 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 AMcourteous
$\displaystyle a|m \Rightarrow m=xa$

$\displaystyle b|m \Rightarrow m=yb$

$\displaystyle 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 AMMedia_Man
Consider: $\displaystyle a|m$, so $\displaystyle m=xa$ for some $\displaystyle x$. Since $\displaystyle b|m$, $\displaystyle b|xa$. Since $\displaystyle a,b$ are coprime, $\displaystyle b\not|a$, nor do they share any factors whatsoever, therefore $\displaystyle b|x$, and $\displaystyle x=yb$ for some $\displaystyle y$. Now $\displaystyle m=xa=yab$, so $\displaystyle ab|m$. QED

Courteous: Consider yourself trivially admonished. - Nov 6th 2009, 08:47 AMDrexel28
Alternatively

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

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