Prove: there exists x and y for c=ax+by iff gcd(a,b)/c.

Answer 1

By Euclid's algorithm, there exists integers n and m, such that:

GCD(a,b) = a n + b m (1)

If GCD(a,b) divides c, then you have that c is some multiple of GCD(a,b). So, we have:

c = p GCD(a,b)

for some integer p. From (1) it then follows that:

c = a n p + b m p = a x + b y

with x = n p and y = m p, so c can indeed be expressed as an integer linear combination of a and b.

Now suppose that we have

c = a x + b y

Clearly a is divisible by GCD(a,b) and so is b. This means that a x is divisible by GCD(a,b) and also b x is divisible by GCD(a,b). Now, if two numbers are divisible by some number q, then the sum of the two numbers will be divisible by q. We can thus conclude that c = a x + b y is divisible by
GCD(a,b).