1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A question about the solution of linear equation

  1. Oct 22, 2007 #1
    I found a rule that the equation ax + by = (a-1)(b-1), for gcd(a, b)=1, has a solution in integers x and y with x ≥ 0 and y≥0, but the equation ax + by = (a-1)(b-1) - 1 don't.
    For example, the equation 3x + 7y = 12 has such soluntion (x, y) = (4, 0), but 3x + 7y = 11 has no such solutions that x and y are integers with x ≥ 0 and y≥0.
    I have verified more a and b, which show my conjecture is correct, but I cann't prove that.
    please help me, thanks.
  2. jcsd
  3. Oct 22, 2007 #2
    You wish to prove that a solution x,y with non-negative x,y, for the equation ax+by = n = ab-a-b+q exists when q=1, and does not exist when q=0. Note that, since gcd(a,b)=1, an integer solution (with x,y possibly negative) always exists (Hardy & Wright, chapter 2, theorem 25).

    If x,y is an integer solution, then y = (n-ax)/b = (ab-a-b+q-ax)/b,
    so that a(x+1)=q (mod b). You might try to play with values of x that yield y >= 0.

    Also, if x,y is a solution, then x+bs, y-as are all solutions, for all integers 's'. So you can pick a pair of 'representative' solutions, one with x in the range 0..b-1, and other with y in the range 0..a-1, and see how this affects the proposal in the previous paragraph.
    Last edited: Oct 22, 2007
  4. Oct 23, 2007 #3
    well, thank your hint, I have proved that.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: A question about the solution of linear equation