Results 1 to 3 of 3

Math Help - Positive Solutions to Linear Diophantine Equation

  1. #1
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485

    Positive Solutions to Linear Diophantine Equation

    I've been looking at the following problem, involving Diophantine equations:

    Let a,b,c\geq 0 such that \gcd(a,b)=1 and c\geq (a-1)(b-1). Show that there exist nonnegative integers s,t so that as+bt=c.

    I know that the solutions to a linear Diophantine equation are given by x=x_0+bt, y=y_0-at, where (x_0,y_0) is a particular solution and t is an integer parameter. If I want these to be positive simultaneously, I need to have \dfrac{-x_0}{b}\leq t\leq \dfrac{y_0}{a}. In other words, there needs to be an integer in the interval \left[\dfrac{-x_0}{b}, \dfrac{y_0}{a}\right].

    From here, I cannot seem to put bounds on the endpoints of the interval. I would appreciate any insight you may have on the issue.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Thanks. I looked into the link provided in the Yahoo answer and was pleasantly surprised to see that the proof given was geometric. I myself spent some time trying to handle the problem geometrically (with a similar approach), but I couldn't get it to work. I should be more careful next time!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Extra Solutions of a Quadratic Diophantine Equation
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 21st 2011, 06:20 AM
  2. Linear system with only positive solutions
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 28th 2011, 01:58 AM
  3. Linear Diophantine equation
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 4th 2008, 07:45 AM
  4. Solutions to this diophantine equation.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 25th 2008, 02:19 PM
  5. Finding all solutions to a Diophantine equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 10th 2006, 02:10 PM

Search Tags


/mathhelpforum @mathhelpforum