Given integers x, y and c. Can I always find integers a and b such that ax + by = c?

Question

Given integers $x$, $y$ and $c$. Can I always find integers a and b such that $ax + by = c$?

This is my exam question. My answers goes like this:

$ax + by = c$

Lets take $x = 2, y = 0$ and $ c = 3$.

so $2a = 3 => a = 3/2 = 1.5$

Therefore $a ∉ ℤ $

Similarly for b. Hence statment is false. Is my counter example correct? Please help. Thanks.

Answer 1

Yes, your counter-example is valid and thus goes part of the way toward showing that the statement in your question is false.

Answer 2

For the more general case, let $x,y$ be arbitrary integers, and let $z = \gcd(x,y)$. Then, if $z$ does not evenly divide $c$, there is no pair of integers $(a,b)$ that satisfy $ax+by=c$. This is because in $\bmod z$, the left side of the equation is congruent to $0$ while the right side is not.

Your example is - at least, technically - not wrong, though one might argue that you have trivialized the problem, since setting $y = 0$ removes the $by$ term, and of course $\gcd(x,0)$ is undefined since there is no such thing as a GCD of $x$ and $0$ (see this post). Another counterexample would be something like $(x,y,z) = (21,14,5)$. Here, $\gcd(21,14) = 7$, and $7$ does not divide $5$, and therefore there is no pair of integers $(a,b)$ that satisfy the equation.

Answer 3

The statement is false, for what refers to the word "always". In fact, the statement is true only if the GCD(x,y) is c. This is the Bézout (1730-1783) identity, and you can find extensive treatments regarding it in the Web. It can be demonstrated, for example, using the Euclidean Algorithm to find the GCD of x and y.

Regarding your counterexample, it eludes the main point, because the GCD of (2,0) is (in my opinion) 2, not c =3, and therefore the two integers a and b, thanks to Bézout, cannot be found. Indeed you can see that if c were = 2, you would have your solution: a =1 and b = any integer.