Results 1 to 3 of 3

Math Help - Prove largest positive integer dividing a and b is 1

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    11

    Prove largest positive integer dividing a and b is 1

    Hey everyone, I can't figure this out (I don't understand how to get there), it seems simple but it is just frustrating the life out of me!

    Let a and b be integers such that 5a - 3b = 1. Prove that the largest positive integer dividing both a and b is 1.

    My professor told me to start by saying "Let d be a positive integer that divides both a and b, then d divides ?"

    It doesn't really help me as I have no idea how to approach this.

    Any help/explanation would be fantastic!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by teacast View Post
    Hey everyone, I can't figure this out (I don't understand how to get there), it seems simple but it is just frustrating the life out of me!

    Let a and b be integers such that 5a - 3b = 1. Prove that the largest positive integer dividing both a and b is 1.

    My professor told me to start by saying "Let d be a positive integer that divides both a and b, then d divides ?"

    It doesn't really help me as I have no idea how to approach this.

    Any help/explanation would be fantastic!
    starting with the hint from your prof we get

    if d|a \implies a=q_1d for some q_1 \in \mathbb{Z}


    if d|b \implies b=q_2d for some q_2 \in \mathbb{Z}

    Now lets plug these into the first equation

    5(q_1d)-3(q_2d)=1 now we can factor out the common d in each term on the left to get

    d(5q_1-3q_2)=1

    Since the integers are closed under addition and subtraction we get that

    dq_3=1 for some q_3 \in \mathbb{Z}

    So this statement tells us that d|1

    The only divisors of 1 are \pm 1 so a and b must be relativley prime.

    TES
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    11
    ohhh I see how you did that, very clever (I wish I could prove like that!).

    One more question, I also have to prove that since r+s, r-s and rs are rational, prove that r/s is rational.

    I said that:

    r = a/b s = c/d

    a/b + c/d = ad+bc/bd

    if b and d do not equal 0, then it is rational



    I did two similar proofs regarding a denominator in r-s and rs,
    not sure if it is right though.... Thanks for the help!
    Last edited by teacast; February 22nd 2009 at 04:50 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 9
    Last Post: April 7th 2010, 12:12 AM
  2. Prove that there exists a positive integer n
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: October 26th 2009, 06:44 PM
  3. Replies: 2
    Last Post: February 5th 2009, 03:27 PM
  4. Replies: 2
    Last Post: October 14th 2007, 06:32 AM
  5. Replies: 12
    Last Post: June 2nd 2007, 03:48 PM

Search Tags


/mathhelpforum @mathhelpforum