Coprime Proof

sirellwood · #1 $Old$ November 5th, 2009, 07:05 AM

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.

courteous · #2 $Old$ November 6th, 2009, 07:58 AM

$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}\frac{1}{y})$

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

(Waiting for their admonishment.)

Meanwhile, is there a [math] tag keyboard shortcut?

Media_Man · #3 $Old$ November 6th, 2009, 08:05 AM

Drexel28 · #4 $Old$ November 6th, 2009, 10:47 AM

Quote:

Originally Posted by sirellwood $View Post$

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$