# greatest common divisor

• Mar 25th 2008, 07:43 AM
deniselim17
greatest common divisor

" If a|bc, then shows that a|[gcd⁡(a,b)∙gcd⁡(a,c)] "

Any suggestions will be very appreciate.
• Mar 25th 2008, 09:36 AM
TheEmptySet
Quote:

Originally Posted by deniselim17

" If a|bc, then shows that a|[gcd⁡(a,b)∙gcd⁡(a,c)] "

Any suggestions will be very appreciate.

Since the gcd of any two numbers can be written as a linear combination we can rewrite each of the above as follows

$\displaystyle \exists \mbox{s,t } \in \mathbb{Z} \ni \mbox{gcd(a,b)} =as+bt$ and

$\displaystyle \exists \mbox{m,n } \in \mathbb{Z} \ni \mbox{gcd(a,c)} =am+cn$

also since $\displaystyle a|bc \iff aq=bc \mbox{ for some } q \in \mathbb{Z}$

so $\displaystyle (gcd(a,b)) \cdot (gcd(a,c))=(as+bt)(am+cn)=a^2sm+acsn+abtm+bctn$

Grouping we get...(and subbing in from above)

$\displaystyle =a(asm+csn+btm)+bctn \iff a(asm+csn+btm) +(aq)tn =$

$\displaystyle a(asm+csn+btm +qtn)$ so finally $\displaystyle a|(asm+csn+btm +qtn) \therefore a|(gcd(a,b)) \cdot (gcd(a,c))$

$\displaystyle QED$