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
The diophantine equation $ax+by = c$ has solutions if and only if $\gcd(a,b)|c$. If so, it has infinitely many solutions, and any one solution can be used to generate all the other ones.

To see this, note that the greatest common divisor of $a$ and $b$ divides both $ax$ and $by$, hence divides $c$ if there is a solution. This gives the necessity of the condition (which you have backwards). (fixed in edits)

The converse is actually a constructive proof, that you can find in pretty much every elementary number theory course or book, and which is essentially the same as yunone's answer above (but without dividing through first).

From the Extended Euclidean Algorithm, given any integers $a$ and $b$ you can find integers $s$ and $t$ such that $as+bt = \gcd(a,b)$; the numbers $s$ and $t$ are not unique, but you only need one pair. Once you find $s$ and $t$, since we are assuming that $\gcd(a,b)$ divides $c$, there exists an integer $k$ such that $\gcd(a,b)k = c$. Multiplying $as+bt=\gcd(a,b)$ through by $k$ you get
$$a(sk) + b(tk) = \gcd(a,b)k = c.$$

So this gives one solution, with $x=sk$ and $y=tk$. 

Now suppose that $ax_1 + by_1 = c$ is a solution, and $ax+by=c$ is some other solution. Taking the difference between the two, we get
$$a(x_1-x) + b(y_1-y) = 0.$$
Therefore, $a(x_1-x) = b(y-y_1)$. That means that $a$ divides $b(y-y_1)$, and therefore $\frac{a}{\gcd(a,b)}$ divides $y-y_1$. Therefore, $y = y_1 + r\frac{a}{\gcd(a,b)}$ for some integer $r$. Substituting into the equation $a(x_1-x) = b(y-y_1)$ gives
$$a(x_1 - x) = rb\left(\frac{a}{\gcd(a,b)}\right)$$
which yields
$$\gcd(a,b)a(x_1-x) = rba$$
or $x = x_1 - r\frac{b}{\gcd(a,b)}$. 

Thus, if $ax_1+by_1 = c$ is any solution, then all solutions are of the form
$$x = x_1 - r\frac{b}{\gcd(a,b)},\qquad y = y_1 + r\frac{a}{\gcd(a,b)}$$
exactly as yunone said.


To give you an example of this in action, suppose we want to find all integer solutions to $$258x + 147y = 369.$$

First, we use the Euclidean Algorithm to find $\gcd(147,258)$; the parenthetical equation on the far right is how we will use this equality after we are done with the computation.
\begin{align*}
258 &amp;= 147(1) + 111 &amp;\quad&amp;\mbox{(equivalently, $111=258 - 147$)}\\
147 &amp;= 111(1) + 36&amp;&amp;\mbox{(equivalently, $36 = 147 - 111$)}\\
111 &amp;= 36(3) + 3&amp;&amp;\mbox{(equivalently, $3 = 111-3(36)$)}\\
36 &amp;= 3(12).
\end{align*}
So $\gcd(147,258)=3$. Since $3|369$, the equation has integral solutions.

Then we find a way of writing $3$ as a linear combination of $147$ and $258$, using the Euclidean algorithm computation above, and the equalities on the far right. We have:
\begin{align*}
3 &amp;= 111 - 3(36)\\
&amp;= 111 - 3(147 - 111) = 4(111) - 3(147)\\
&amp;= 4(258 - 147) - 3(147)\\
&amp;= 4(258) -7(147).
\end{align*}
Then, we take $258(4) + 147(-7)=3$, and multiply through by $123$; why $123$? Because $3\times 123 = 369$. We get:
$$258(492) + 147(-861) = 369.$$
So one solution is $x=492$ and $y=-861$. All other solutions will have the form
\begin{align*}
x &amp;= 492 - \frac{147r}{3} = 492 - 49r,\\
y &amp;= -861 + \frac{258r}{3} =86r - 861, &amp;\qquad&amp;r\in\mathbb{Z}.
\end{align*}
You can reduce those constants by making a simple change of variable. For example, if we let $r=t+10$, then 
\begin{align*}
x &amp;= 492 - 49(t+10) = 2 - 49t,\\
y &amp;= 86(t+10) - 861 = 86t - 1,&amp;\qquad&amp;t\in\mathbb{Z}.
\end{align*}
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.