Prove: there exists x and y for c=ax+by iff gcd(a,b)/c.
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).