# [SOLVED] Simple proof

• Aug 5th 2009, 08:49 AM
diddledabble
[SOLVED] Simple proof
Show that if $\displaystyle a\mid{c}$ and $\displaystyle b\mid{c}$ then $\displaystyle ab\mid{c}$

I got started and have Let c=ae and c=bd where d and e are integers.
c=ae=bd and a and b are not equal then e=b and d=a thus $\displaystyle ab\mid{c}$ where the result would be 1.
I am pretty sure my logic is really messed up though.
• Aug 5th 2009, 08:56 AM
Plato
Quote:

Originally Posted by diddledabble
Show that if $\displaystyle a\mid{c}$ and $\displaystyle b\mid{c}$ then $\displaystyle ab\mid{c}$

$\displaystyle 3\mid12~\&~6\mid 12\text{ but is it true that }18\mid 12?$
• Aug 5th 2009, 08:59 AM
diddledabble
I forgot to add that gcd (a,b)=1 Sorry.
• Aug 5th 2009, 09:14 AM
mikeyS
In your equations c=ae and c=bd try solving for a and b then look and the product of the two.

That should get ya there
• Aug 5th 2009, 09:23 AM
diddledabble
So then $\displaystyle a=c/e$ and $\displaystyle b=c/d$ then $\displaystyle ab=e/d$ Where $\displaystyle e/d=c$ Is that correct?
• Aug 5th 2009, 09:53 AM
Gamma
Proof
$\displaystyle (a,b)=1\Rightarrow \exists s,t\in \mathbb{Z} s.t. as+bt=1$

Multiply through by c to arrive at
$\displaystyle asc+btc=c$

ab|asc because a|a and b|c

ab|btc because a|c and b|b

so it divides the sum which is c as desired.
• Aug 5th 2009, 10:17 AM
mikeyS
Quote:

Originally Posted by diddledabble
So then $\displaystyle a=c/e$ and $\displaystyle b=c/d$ then $\displaystyle ab=e/d$ Where $\displaystyle e/d=c$ Is that correct?

I take back my original post. Let's try another approach.

Since gcd(a,b) = 1 then there exists integers $\displaystyle x,y$ such that $\displaystyle 1=ax+by$

Multiply this equation by c to yield
1) $\displaystyle c*1 = c = c(ax+by)=axc+byc$

Now $\displaystyle c=ak=bl$ where $\displaystyle k,l$ are integers

Substitute these values in equation 1)
$\displaystyle c=ax(bl)+by(ak)=abxl+abyk=ab(xl+yk)=abm$ where $\displaystyle m$ is an integer

Thus $\displaystyle c=abm$ or equivalently $\displaystyle ab|c$