Results 1 to 2 of 2

Math Help - greatest common divisor

  1. #1
    Member
    Joined
    Mar 2008
    Posts
    83

    Question 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by deniselim17 View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest Common Divisor of (9m+8, 6m+5)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 15th 2011, 05:43 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  3. Greatest Common Divisor.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 23rd 2009, 12:36 AM
  4. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 17th 2009, 07:16 PM
  5. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 03:24 AM

Search Tags


/mathhelpforum @mathhelpforum