Results 1 to 5 of 5

Math Help - Probably an easy gcd proof

  1. #1
    Newbie
    Joined
    Apr 2007
    Posts
    3

    Probably an easy gcd proof

    I have to prove that if a and b are relatively prime, gcd(ac,b) = gcd(c,b)

    This is simple enough if you use the idea of prime factorization, but i've been specifically instructed not to resort to prime factorization.

    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member frenzy's Avatar
    Joined
    Mar 2007
    From
    Planet Express
    Posts
    58
    Quote Originally Posted by Ryan View Post
    I have to prove that if a and b are relatively prime, gcd(ac,b) = gcd(c,b)

    This is simple enough if you use the idea of prime factorization, but i've been specifically instructed not to resort to prime factorization.

    Thanks in advance
    since gcd(a,b)=1

    qa+wb=1

    assume gcd(c,b)=d

    then

    ec+rb=d

    ec*1+rb=d

    ec*(qa+wb)+rb=d

    (eq)(ac)+(ecw)b+rb=d

    (eq)(ac)+((ecw)+r)b=d

    also note:gcd(ac,b)>=gcd(c,b)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2007
    Posts
    3
    First off, thanks

    I follow what you've done but how do we know that d is necessarily the greatest common divisor of ac and b? I'm assuming I need to use the fact that gcd(ac,b)>=gcd(c,b) but I'm not quite sure where to go with that
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member frenzy's Avatar
    Joined
    Mar 2007
    From
    Planet Express
    Posts
    58
    First, we know that gcd(c,b)=d

    and that gcd(ac,b)>=gcd(c,b) (do you believe this)

    we found a linear combination of ac and b such that it equaled d.

    therefore gcd(ac,b)<=d (we might be able to find a positive l.c. of ac and b that is less than d) but we can't since

    d>=gcd(ac,b)>=gcd(c,b)=d
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2007
    Posts
    3
    Now I follow, this makes perfect sense. I appreciate your help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Very easy proof
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: May 11th 2011, 12:35 PM
  2. Need help on an easy proof for everyone
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 7th 2010, 04:11 AM
  3. Need help on an easy proof
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: February 23rd 2010, 10:30 PM
  4. Easy Proof
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: June 19th 2009, 10:05 PM
  5. Easy Proof Help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 31st 2007, 02:25 PM

Search Tags


/mathhelpforum @mathhelpforum