Question

Let$a,b,c\in \mathrm{\mathbb{Z}}$. Prove that the equation$ax+by=c$ has integer solution if and only if$\left(a,b\right)|c$ .

Short answer

The equation has integer solutions $ax+by=c$ if and only if $\left(a,b\right)|c$.

Step-by-step solution

Linear Combination: 

Let $d$ be the largest integer that divides the integers $aandb$. Then there exist integerssuch that:

$d=au+bv$

Where $a,b\ne 0$.

Proof using Theorem 1.3: 

Let,$d=\left(a,b\right)$,

Then, using the definition of linear combination, for $d|c$, we get:

role="math" localid="1646287727077" $c=dw,\dots \dots \dots \dots \left\{w\in \mathrm{\mathbb{Z}}\right\}$

Then using theorem 1.3, we have:

$$\begin{gathered} d=au+bv \\ dw=auw+bvw \\ c=ax+by\dots \dots \dots \dots \left\{letuw=xandvw=y\right\} \end{gathered}$$

Thus, if $\left(a,b\right)|c$, we have:

$c=ax+by$

Hence, it is proved that the equation has integer solutions $ax+by=c$if and only if and only if $\left(a,b\right)|c$.