# greatest common divisor

Printable View

• Mar 25th 2008, 07:43 AM
deniselim17
greatest common divisor
Can anyone please help me with this proof?

" 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
Can anyone please help me with this proof?

" 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

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

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

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

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

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

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

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

$QED$