# Determining the existence of an integral linear combination

Given $x, y, r \in \mathbb{Z}$, how can you tell whether there exist two integers $a$ and $b$ such that $ax + by = r$?

That is, how do you determine whether an integral linear combination exists for $x$, $y$, and $r$?

-
Extended Euclidean algorithm? – Ganesh Oct 21 '12 at 2:26

Consider $d = \gcd(x, y)$.
$$\textrm{Then} \; \frac{ax + by}{d} =\frac{r}{d}, \frac{ax + by}{d} \in \mathbb{Z}$$
If $d$ does not divide $r$, there exist no possible $a, b \in \mathbb{Z}$. If $d$ divides $r$, the solution can be found by the Extended Euclidean Algorithm. Thanks to Ganesh for pointing me in the right direction.