Results 1 to 5 of 5

Math Help - Proof on Integers, sa+tb=n

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    9

    Proof on Integers, sa+tb=n

    The problem: Let a,b be coprime positive integers. Prove that for any integer n there exists s,t with s>0 such that sa+ tb=n.



    My work so far (do not know if I am on the right path):


    If a,b are coprime there exists s,t in the integers that sa+tb=1.
    This is by definition that is given in our text.
    Since, in addition, a,b are positive integers then there are two possible scenarios for s,t as follows:
    1. s>0 and t<0
    2.s<0 and t>0


    This problem has given me a headache
    I will greatly appreciate your feedback!

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Hint: Note that you also have some x and y, such that xa + yb = 0
    Can you now take it fwd?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    9

    i think.

    I'll try to break the problem up into cases.

    One for n being postiive
    One for n being zero
    One for n being negative

    Then for all the cases I will show that there is a set of s and t's such that the coefficient in front of the a term will be positive.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    I'd like to point out that your original attempt actually doesn't help. There will be some positive and negative s that satisfy the equation; that is, the equation can be satisfied in both cases.

    One route that you could try is geometric: consider as+bt=n as a line on the st-plane. Finding integer solutions to the equation means finding integer points that lie on the line. The main question is, where are the integer points on the line? You might like to try a few numerical examples and then make guess in general.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773
    I'd like to point out that your original attempt actually doesn't help.
    I don't agree. I think that the idea that sa + tb = 1 for some s, t together with the remark that xa + yb = 0 for some x, y allow finishing the proof. I would add that one can choose to have x > 0, y < 0 or x < 0, y > 0. Using xa + yb = 0, one can "pump" the coefficient of a in sa + tb = 1 to make it have the correct sign.

    If a,b are coprime there exists s,t in the integers that sa+tb=1.
    This is by definition that is given in our text.
    I doubt that this is the definition of coprime numbers. It is probably a fact that is proved afterwards.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof about integers
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 14th 2010, 08:14 AM
  2. set of odd integers proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 25th 2010, 08:21 AM
  3. integers proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 7th 2010, 05:46 PM
  4. Proof of integers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 10th 2009, 02:33 PM
  5. Integers and proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 18th 2009, 08:39 AM

Search Tags


/mathhelpforum @mathhelpforum