Question

Let a and b be positive integers, and let d be their greatest common divisor. Prove that there are infinitely many integers x and y such that ax+by = d. Next, given one particular solution x0 and y0 of this equation, show how to find all the solutions.

Answer 1

The equation ax+by=c has solutions if and only if gcd(a,b)|c.

If so, it has infinitely many solutions, and any one solution can be used to generate all the other ones.

the greatest common divisor of a and b divides both ax and by,

hence divides c , if there is a solution.

given any integers a and b you can find integers v and w such that av+bw =gcd(a,b); the numbers v and w are not unique, but you only need one pair.

Once you find v and w, since we are assuming that gcd(a,b) divides c, there exists an integer "m" such that gcd(a,b)m=c . Multiplying av+bw=gcd(a,b) through by m you get

a(vm)+b(wm)=gcd(a,b)m=c.  

this gives one solution, with x=vm  and y=wm.

suppose that ax₁+by₁=c is a solution, and ax+by=c is some other solution.

Taking the difference between the two equation ( ax₁+by₁=c & ax+by=c),

  a(x₁−x)+b(y₁−y)=0. Therefore, a(x₁−x)=b(y−y₁)

means that a divides b(y−y₁), and therefore    divides y−y₁.

Therefore,   for some integer r. Substituting into the equation a(x₁−x)=b(y−y₁) gives

which give   or .

So,

if ax₁+by₁=cax₁+by₁=c is any solution,

then all solutions are of the form and  .

so this is the proof that there are infinitely many integers x and y such that ax+by = d.