Results 1 to 4 of 4

Math Help - Prove if ad - bc = 1 or -1, then gcd(a+b, c+d) = 1

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    79

    Prove if ad - bc = 1 or -1, then gcd(a+b, c+d) = 1

    Problem:
    Show that if ad - bc = 1 or -1, then gcd(a+b, c+d) = 1.

    Work so far:
    I know that since a(d) + b(-c) = 1 or -1, then the gcd(a,b) = 1. The same can be also said to show gcd(c,d) = 1, gcd(a,c) = 1, and gcd(b,d) = 1. I also know that gcd(a+b, c+d) divides a+b and c+d, so it will divide any linear combination of a+b and c+d.
    I'm really at a loss of where to go from here.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by uberbandgeek6 View Post
    Problem:
    Show that if ad - bc = 1 or -1, then gcd(a+b, c+d) = 1.

    Work so far:
    I know that since a(d) + b(-c) = 1 or -1, then the gcd(a,b) = 1. The same can be also said to show gcd(c,d) = 1, gcd(a,c) = 1, and gcd(b,d) = 1. I also know that gcd(a+b, c+d) divides a+b and c+d, so it will divide any linear combination of a+b and c+d.
    I'm really at a loss of where to go from here.


    The equality \displaystyle{ab+(-cd)=\pm 1 means that  gcd(a,c)=gcd(a,d)=gcd(b,c)=gcd(b,d)=1 .

    Take it from here.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2011
    Posts
    71
    It seems like you know that if you can write ax+by=1 for integers a,b, then gcd(x,y)=1. Can you express ad-bc as a linear combination of (a+b) and (c+d)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    It's enough to express 1 as a linear combination of a+b and c+d.

    By inspection (a+b)d+(-b)(c+d)=ad+bd-bc-bd=1.
    Then (a+b)(-d)+(b)(c+d)=-1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove that
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 21st 2010, 05:48 AM
  2. Prove n^2<= ......
    Posted in the Advanced Algebra Forum
    Replies: 12
    Last Post: November 17th 2009, 05:52 AM
  3. Replies: 2
    Last Post: August 28th 2009, 02:59 AM
  4. prove that
    Posted in the Algebra Forum
    Replies: 4
    Last Post: September 7th 2008, 05:14 PM
  5. prove
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 7th 2008, 01:45 PM

Search Tags


/mathhelpforum @mathhelpforum