# greatest common divisor

• Mar 25th 2008, 08: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, 10: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

$\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$
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 8, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}