1
$\begingroup$

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$?

  • 1
    Extended Euclidean algorithm?2012-10-21

1 Answers 1

3

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.