GCD question?

Question

If anyone could explain how the following is done, it would be greatly appreciated!

Suppose that the gcd(a,b)=1. Prove that for every integer c, the equation ax+by = c has a solution in integers x and y (by finding a solution to au+bv=1 and multiplying by c).

Answer 1

First, note that the follow equation has NO integral soluitons:

2x + 6y = 1.

They have no solutions because the left side is divisible by 2 but ,the right side is not (do you see that is the case?). In this particular eqution (a,b) =2 and consequently ax + by will always have to be a multiple of (a,b)=2.

In order for ax+by =c to have a soltion for all integer values of c in must be the case that every choice for c be a multiple of (a,b). The only possibility that canrk is iff(a,b) =1.

Answer 2

this a quite involved topic. it's called diophantine equations.
go to ask dr.math:
http://mathforum.org/library/drmath/view/51595.html
or for a more formal explanation,
http://mathworld.wolfram.com/
and search for diophantine equation.

dr math has a simpler, more colloquial explanation.

the strategy for solving ax+by =c involves solving ax +by = 1 using the euclid gcd algorithm as you can see from these sites.