<s>[INST] How to find solutions of linear Diophantine ax + by = c? I want to find a set of integer solutions of Diophantine equation: $ax + by = c$, and apparently $\gcd(a,b)|c$. Then by what formula can I use to find $x$ and $y$ ? 
I tried to play around with it:
$x = (c - by)/a$, hence $a|(c - by)$.   
$a$, $c$ and $b$ are known. So to obtain integer solution for $a$, then $c - by = ak$, and I lost from here, because $y = (c - ak)/b$. I kept repeating this routine and could not find a way to get rid of it? Any hint?
Thanks,
Chan
 [/INST] Look can be deceiving. The integer solution to the equation $ax + by = c$ is anything but easy. Please endure a rather long derivation.
To make it more comprehensible let's first solve the equation for y:
\begin{align*}
ax + by = c\\
by = c - ax\\
y = \frac{c - ax}{b}
\end{align*}
To have an integer solution, $y$ must be an integer, and that is if $c - ax$ is a multiple of $b$, or $c - ax = -nb \iff ax = c + nb$. This has the same meaning as $ax \equiv c \: (mod \: n)$.
To continue, we need this Theorem 1:

The congruence $ax \equiv c \: (mod \: n)$ has a solution iff $gcd(a, n) \: | \: c$.

And this Lemma 2:

If $gcd(p, q) = 1$, then $px \equiv r \: (mod \: q)$ has a solution modulo $q$.

To keep this answer manageable, I would like to skip the proof of Theorem 1 and Lemma 2 (which can be found by googling). Just post a question and comment me if you encounter some trouble with them.
Let's define $d = gcd(a, n)$, and continue the derivation:
\begin{align*}
ax \equiv c \: (mod \: n)\\
ax = c + bn\\
\frac{a}{d} x = \frac{c}{d} + \frac{b}{d} n
\end{align*}
Now we want to switch $b$ and $n$ so $\frac{n}{d}$ could be seen more clearly as the modulo and continue it as following:
\begin{align*}
\frac{a}{d} x = \frac{c}{d} + b \frac{n}{d}\\
\frac{a}{d} x \equiv \frac{c}{d} \: (mod \: \frac{n}{d})
\end{align*}
Note that $\frac{a}{d}$ and $\frac{n}{d}$ from our derivation above is the $p$ and $q$ in the Lemma 2 respectively. Also note that as $d$ is $gcd(a, n)$, so $gcd(\frac{a}{d}, \frac{n}{d}) = 1$. Hence by Lemma 2:
\begin{align*}
\frac{a}{d} x \equiv \frac{c}{d} \: (mod \: \frac{n}{d})
\end{align*}
is our solution to equation $ax + by = c$.

As an example, let us solve $6x - 10y = 4 \iff 6x = 4 + 10y \iff 6x ≡ 4 \: (mod \: 10)$. $Gcd(6, 10) = 2$, and $2 \: | \: 4$, so by Theorem 1 that equation has a solution.
From our derivation, the solution is $\frac{6}{2} x = \frac{4}{2} \: (mod \: \frac{10}{2}) \iff 3x = 2 \: (mod \: 5)$.
By Lemma 2, we have a solution $modulo \: 5$. What it means is if we write the solution in $Z_5$, we would have:
\begin{align*}
\bar{3} \bar{x} = \bar{2}\\
\bar{x} = \bar{3}^{-1} \: \bar{2}
\end{align*}
As in $Z_5$, $\bar{3} \: \bar{2} = \bar{1} = \bar{3} \: \bar{3}^{-1}$, so $\bar{3}^{-1} = \bar{2}$ and we have:
\begin{align*}
\bar{x} = \bar{3}^{-1} \: \bar{2}\\
\bar{x} = \bar{2} \: \bar{2} = \bar{4}
\end{align*}
In $Z_5$, $\bar{x} = \bar{4} \iff x \equiv 4 \: (mod \: 5) \iff x = 4 + 5s \iff x = 4, 9, 13, \cdots$. You can check that indeed $x \equiv 4 \: (mod \:5)$ is the solution.
</s>