# A question about the solution of linear equation

1. Oct 22, 2007

### whodsow

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.

2. Oct 22, 2007

### dodo

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
3. Oct 23, 2007

### whodsow

well, thank your hint, I have proved that.