Results 1 to 4 of 4

Math Help - GCD Proof

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    1

    GCD Proof

    I had two questions I can't figure out...

    1) prove that if gcd(a,b) = 1 then gcd(a+b,a*b) = 1

    2) let gcd(a,b) = 1. prove that d= gcd(a+b, a-b) = 1 or 2
    (hint: prove d<2)

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by tips0517 View Post
    I had two questions I can't figure out...

    1) prove that if gcd(a,b) = 1 then gcd(a+b,a*b) = 1
    Let d=gcd(a+b,a*b)

    Then d divides (a+b)x+(a*b)y, where x and y can be any integers.

    If you let x=a and y=-1, you get : a+ab-ab=a. Thus d divides a

    If you let x=b and y=-1, you get : ab+b-ab=b. Thus d divides b

    ---> d=1.


    2) let gcd(a,b) = 1. prove that d= gcd(a+b, a-b) = 1 or 2
    (hint: prove d<2)

    Thanks!
    d divides (a+b) and (a-b) and thus divides (a+b)+(a-b)=2a and (a+b)-(a-b)=2b.
    So d divides 2 or d divides a. If it doesn't divide 2, it divides a and b. Then...

    If it divides 2, then...
    Last edited by Moo; September 9th 2008 at 12:34 PM. Reason: moodification
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Quote Originally Posted by Moo View Post
    d divides … 2a …
    So d divides 2 or d divides a.
    That would only be true if d = 1 or a prime. It is not true for general integers d.

    Quote Originally Posted by tips0517 View Post
    2) let gcd(a,b) = 1. prove that d= gcd(a+b, a-b) = 1 or 2
    (hint: prove d<2)
    \gcd(a,b)=1 \Rightarrow \exists\,r,s\in\mathbb{Z} with ra+sb=1.

    Hence r\left[(a+b)+(a-b)\right]+s\left[(a+b)-(a-b)\right] = 2(ra+sb) = 2.

    \therefore\ d divides 2 since d divides the LHS.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by tips0517 View Post
    I

    1) prove that if gcd(a,b) = 1 then gcd(a+b,a*b) = 1
    Suppose \gcd(a+b,ab) \ne 1, and p be a prime divisor of a+b and ab. Then as \gcd(a,b)=1 p|a and p \not| b or p \not |a and p| b.

    Without loss of generality suppose the first of these is the case. Then p \not| (a+b) , a contradiction so no such prime can exist and \gcd(a+b, ab)=1.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 09:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum