Example

Suppose $\gcd(a,b)=1$. Prove that $ax+by=c$ has integer solutions $x$ and $y$ for every integer $c$, then find a solution to $37x+47y=103$ where $x$ and $y$ are as small as possible.


Given that $\gcd(a,b)=1$, we know that $ax+by=1$ has integer solutions $x=x_0$ and $y=y_0$ that can be found using the Euclidean Algorithm. Now consider $x=cx_0$ and $y=cy_0$. Notice that

$$\begin{align} ax+by&=cax_0+cby_0\\ &=c(ax_0+by_0)\\ &=c \cdot 1\\ &= c \end{align}$$

Hence, $ax+by=c$ always has a solution for every integer $c$.

As for $37x+47y=103$, $x=-15$ and $y=14$ gives the smallest sum $x+y$.