Results 1 to 9 of 9

Math Help - Prove these two GCD (greatest common divisor)

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    9

    Prove these two GCD (greatest common divisor)

    Hi, thanks for taking the time to look in this thread. Here are the GCD (great common divisior) questions that need proof:


    1. Let a and b be integers. Prove that gcd(a, b)|gcd(a + b, a − b).

    2. Let a, b, c be integers. Suppose that gcd(a, b) = 1 and c|(a+b). Prove
    that gcd(a, c) = 1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by jessicafreeman View Post
    Hi, thanks for taking the time to look in this thread. Here are the GCD (great common divisior) questions that need proof:


    1. Let a and b be integers. Prove that gcd(a, b)|gcd(a + b, a − b).

    2. Let a, b, c be integers. Suppose that gcd(a, b) = 1 and c|(a+b). Prove
    that gcd(a, c) = 1.
    what have you tried?

    first recall that the gcd of two integers can be written as a (in fact, the smallest) linear combination of the two integers.

    also recall what it means for one integer to divide another. a \mid b \Longleftrightarrow b = ka for some k \in \mathbb Z

    you think you can get anywhere with those? or do you need another hint?


    for 1 i'd start this way: all variables are integers here

    Let d = \text{gcd}(a+b,a-b) and d_1 = \text{gcd}(a,b). You want to show that d = kd_1 for some k.

    Now, d = r(a + b) + t(a - b) = \cdots

    use the fact that d_1 = \text{gcd}(a,b) to finish up.


    for 2, since \text{gcd}(a,b) = 1, we have that

    1 = ma + nb for some m,n

    you want to show that ra + tc = 1 for some r,t. use the fact that c \mid (a + b) to accomplish this (start by translating that into an equation)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    9
    Thank you for your help Jhevron.

    I was able to solve question 2, but I still haven't quite got the final proof for 1...

    is there any other small hint you could throw my way, if possible? if not, thats ok. thank you for all your help!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by jessicafreeman View Post
    Thank you for your help Jhevron.

    I was able to solve question 2, but I still haven't quite got the final proof for 1...

    is there any other small hint you could throw my way, if possible? if not, thats ok. thank you for all your help!
    good job on problem 2. if you like, you can post your solution to be scrutinized.

    as for an additional hint for 1: d_1 = \text{gcd}(a,b) means, in particular, d_1 \mid a and d_1 \mid b. And what do each of those mean? Can you use that to finish up?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2010
    Posts
    9
    argh! Oh dear, i made a mistake... i meant to say that the other way around x__x. I finished problem 1 and didn't completely get problem 2 .

    thank you though.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by jessicafreeman View Post
    argh! Oh dear, i made a mistake... i meant to say that the other way around x__x. I finished problem 1 and didn't completely get problem 2 .

    thank you though.
    essentially the same hint will work. c|(a + b) \Longleftrightarrow a + b = kc for some integer k. what can you do with that equation?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2010
    Posts
    9
    Quote Originally Posted by Jhevon View Post
    essentially the same hint will work. c|(a + b) \Longleftrightarrow a + b = kc for some integer k. what can you do with that equation?
    hehe thanks.

    the result i found with how it ended up was being something of the form
    1= a(k-j) + c(rk), where k, j, r, and k are some integers...
    i'm worried that it's wrong because there's too many variables on c .
    Follow Math Help Forum on Facebook and Google+

  8. #8
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by jessicafreeman View Post
    hehe thanks.

    the result i found with how it ended up was being something of the form
    1= a(k-j) + c(rk), where k, j, r, and k are some integers...
    i'm worried that it's wrong because there's too many variables on c .
    you have the desired form, so we're good. you have an integer times a plus and integer times c equals 1. you seemed to use different variables than i did, but yeah, i got something like that.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jan 2010
    Posts
    9
    Quote Originally Posted by Jhevon View Post
    you have the desired form, so we're good. you have an integer times a plus and integer times c equals 1. you seemed to use different variables than i did, but yeah, i got something like that.

    yay! thank you so much! i really appreciate all your help!
    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, 06:43 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 06:45 AM
  3. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 17th 2009, 08:16 PM
  4. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 04:24 AM
  5. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 16th 2006, 03:56 PM

Search Tags


/mathhelpforum @mathhelpforum