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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook