Results 1 to 3 of 3

Math Help - gcd proofs

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    13

    gcd proofs

    Hi all, have a couple of gcd proofs that I'm stuck with.

    1=If gcd(a,c)=1 and gcd(b,c)=1 then gcd(ab,c)=1

    thus far all I can figure is to do the following linear combos:
    1- ax+cy=1
    2-bu+cv=1
    3-abz+ct=1
    But then I don't know what to do. I try solving for c in one of them and then substituting, but this leads nowhere.

    2- If a|c and b|c and gcd(a,b)=1 then ab|c.
    This is similar to 1, so I'm also stuck with this one.

    Any help would be appreciated. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by jusstjoe View Post
    Hi all, have a couple of gcd proofs that I'm stuck with.

    1=If gcd(a,c)=1 and gcd(b,c)=1 then gcd(ab,c)=1

    thus far all I can figure is to do the following linear combos:
    1- ax+cy=1
    2-bu+cv=1
    3-abz+ct=1
    But then I don't know what to do. I try solving for c in one of them and then substituting, but this leads nowhere.

    2- If a|c and b|c and gcd(a,b)=1 then ab|c.
    This is similar to 1, so I'm also stuck with this one.

    Any help would be appreciated. Thanks!
    Hi jusstjoe.

    (1) You have

    ax+cy\ =\ 1
    bu+cv\ =\ 1

    Now multiply them together:

    1\ =\ (ax+cy)(bu+cv)\ =\ ab(ux)+c(avx+buy+cvy)

    Thus \gcd(ab,c)=1.

    (2) If \gcd(a,b)=1, then \mathrm{lcm}(a,b)=ab. The rest follows from the definition of LCM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2009
    Posts
    3

    What about this Proof?

    Nice Proof, very helpful!
    Last edited by tyelford; June 2nd 2009 at 08:55 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proofs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 2nd 2010, 03:54 AM
  2. lim sup and lim inf proofs
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: February 24th 2010, 07:02 PM
  3. More Proofs
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 13th 2008, 07:05 PM
  4. Proofs
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 3rd 2008, 04:23 AM
  5. Replies: 3
    Last Post: October 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum