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.

Printable View

- Mar 25th 2008, 07:43 AMdeniselim17greatest 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 AMTheEmptySet
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$