Positive Solutions to linear diophantine equation

Let a,b,m,n be integers > 0, let integer k >= 0. define g = gcd(a,b)

Theorem: am + bn = ab/g + g + kg has a solution m,n, given a,b,k. (eqn 1)

Proof: n must have a value such that ab/g + g + kg -bn is divisible by a. This can be accomplished by selecting n to be in the set {1,2,... a/g}. One of these numbers is sufficient because

ab/g + g + kg has only a/g possible residues (mod a/g).

We need to show that m>=1 is possible. The maximum value of bn is ba/g. So

am >= ab/g + g + kg -ab/g = g + kg (eqn 2)

m >= g/a + kg/a (eqn 3)

g/a > 0 is so m >= 1. Any k>0 can only help this.

Notice that if the +g term is ommited from (eqn 1), then (eqn 3) becomes m >= kg/a (eqn 4), thus m=0 cannot be ruled out. So (eqn 1) is the best we can do. Q.E.D

Special case, There are non-negative solutions starting at n=(a-1)(b-1)

x>=0,y>=0,g=1

applying the theorem with m=x+1, n=y+1;

a(x+1)+b(y+1)=ab+1+k

ax+by = (a-1)(b-1) + k

This is a common form of the problem.

http://www.efnet-math.org/w/Positive_Solutions_to_linear_diophantine_equation