# 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 &= 147(1) + 111 &\quad&\mbox{(equivalently, $111=258 - 147$)}\\ 147 &= 111(1) + 36&&\mbox{(equivalently, $36 = 147 - 111$)}\\ 111 &= 36(3) + 3&&\mbox{(equivalently, $3 = 111-3(36)$)}\\ 36 &= 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 &= 111 - 3(36)\\ &= 111 - 3(147 - 111) = 4(111) - 3(147)\\ &= 4(258 - 147) - 3(147)\\ &= 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 &= 492 - \frac{147r}{3} = 492 - 49r,\\ y &= -861 + \frac{258r}{3} =86r - 861, &\qquad&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 &= 492 - 49(t+10) = 2 - 49t,\\ y &= 86(t+10) - 861 = 86t - 1,&\qquad&t\in\mathbb{Z}. \end{align*}

• is it possible to add a little discussion around same equation in higher dimensions ? Jun 25, 2016 at 12:59
• @Cookie: I wrote this eight years ago... As to your question:No, you cannot write $\frac{a}{b}$, because you do not know that $b$ divides $a$. That’s precisely the issue. By writing $\frac{a}{b}$ you are leaving the integers and going into the rationals. Let $d=\gcd(a,b)$. Write $a=da’$, $b=db’$. Then it is well known that $\gcd(a’,b’)=1$. From $a|b(y-y_1)$ you get $a’|b’(y-y_1)$. And since $\gcd(a’,b’)=1$< you deduce $a’|y-y_1$. This is pretty standard fare. Mar 19, 2019 at 2:57
• @ArturoMagidin How does $a(x_1-x) = b(y-y_1)$ mean that $a$ divides $b(y-y_1)$? How can we be sure $a$ always divides $b(y-y_1)$ and $(x_1-x)$ does not divide $b(y-y_1)$?
– alu
Sep 7, 2020 at 15:00
• @alu: Huh? By definition, $a$ divides $b(y-y_1)$ if and only if there exists an integer $k$ such that $ak=b(y-y_1)$. Here, the integer is $x_1-x$. Sep 7, 2020 at 15:16
• @alu: Note: both $a$ and $x-x_1$ divide $b(y-y_1)$. It’s not a “one or the other”. $2\times 3= 6$, so both $2$ and $3$ divide $6$. Sep 7, 2020 at 18:03

As others have mentioned one may employ the extended Euclidean algorithm. It deserves to be better known that this is most easily performed via row-reduction on an augmented matrix - analogous to methods used in linear algebra. See this excerpt from one of my old sci.math posts:

For example, to solve  mx + ny = gcd(x,y) one begins with
two rows  [m   1    0], [n   0    1], representing the two
equations  m = 1m + 0n,  n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,

Here is an example:  d =  x(80) + y(62)  proceeds as:

in equation form   | in row form
---------------------+------------
80 =   1(80) + 0(62) | 80   1   0
62 =   0(80) + 1(62) | 62   0   1
row1 -   row2  ->  18 =   1(80) - 1(62) | 18   1  -1
row2 - 3 row3  ->   8 =  -3(80) + 4(62) |  8  -3   4
row3 - 2 row4  ->   2 =   7(80) - 9(62) |  2   7  -9
row4 - 4 row5  ->   0 = -31(80) +40(62) |  0 -31  40


Above the row operations are those resulting from applying the Euclidean algorithm to the numbers in the first column,

        row1 row2 row3 row4 row5
namely:  80,  62,  18,   8,   2  = Euclidean remainder sequence
|    |
for example   62-3(18) = 8, the 2nd step in Euclidean algorithm

becomes:   row2 -3 row3 = row4  on the identity-augmented matrix.

In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:

[  7 -9] [ 80  1  0]  =  [2   7  -9]
[-31 40] [ 62  0  1]     [0 -31  40]

The 1st row is the particular  solution: 2 =   7(80) -  9(62)
The 2nd row is the homogeneous solution: 0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:

n row1 + m row2  ->  2n = (7n-31m) 80 + (40m-9n) 62

The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field,
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form,
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.

• Thanks, I really like your Linear Algebra approach. Feb 6, 2011 at 21:54
• @Chan: It irks me that most textbooks in elementary number theory present more obfuscated approaches. If you go on to study algebra you will learn more about the underlying theory when you study Hermite Smith normal forms and other module-theoretic generalizations of linear algebra results. Feb 6, 2011 at 22:06
• This is actually discussed in Niven, Zuckerman, Montgomery. Just so you have a reference (pages 217-218 in the 5th edition). Feb 6, 2011 at 22:07
• @Arturo. Thanks for the reference. I'm happy to see that it finally made it into an edition of a popular textbook, but I'm sad that the presentation there leaves much to be desired. Feb 6, 2011 at 22:21
• I don't mean to be a smart-aleck, or too pedantic, but in your first grey sandbox, you have written 0=-31(80)-40(62) in the "in equation form" column, when I think it should instead be: 0=-31(80)+40(62). Apr 8, 2022 at 5:28

Here's another method. It doesn't require finding an initial solution, but it may require finding a modular multiplicative inverse. (Edit: I'll show this method with an example instead of a generalization. It may make it more clear.)

Solve $2x+3y=5$.

$2x\equiv 5\pmod{3}$.

You could either find a multiplicative inverse:

$x\equiv 5\cdot 2^{-1}\pmod{3}$

Or do it as follows:

$2x\equiv 2\pmod{3}$

Divide both sides by $2$ (notice $\gcd(3,2)=1$).

$x\equiv 1\pmod{3}$, $x=3n+1$, $n\in\mathbb Z$.

Substitute this value of $x$ into the original equation:

$2(3n+1)+3y=5$, $y=1-2n$.

Answer: $(x,y)=(3n+1,1-2n)$, $n\in\mathbb Z$.

• I think this is a great ans and I will use it a lot :D Feb 25, 2019 at 1:34
• This answer deserves to be on top. Really great answer, made me realize that linear congruences and diophantine equations are inter-convertible. Sep 11, 2019 at 14:25

Do you mean $\gcd(a,b)$ divides $c$? If so, you can divide both sides of the equation to get $$\frac{a}{g}x+\frac{b}{g}y=\frac{c}{g}$$ where $g=\gcd(a,b)$.

But since $\gcd(a/g,b/g)=1$, you can use the extended Euclidean algorithm to find a solution $(x_0,y_0)$ to the equation $$\frac{a}{g}x+\frac{b}{g}y=1.$$

Once you have that, the solution $(X,Y)=(\frac{c}{g}\cdot x_0,\frac{c}{g}\cdot y_0)$ is a solution to your original equation. Furthermore, the values $$x=X + \frac{b}{g} t\quad y=Y - \frac{a}{g} t$$ give all solutions when $t$ ranges over $\mathbb{Z}$, I believe.

• @yuone: Yes, that gives all solutions. Feb 6, 2011 at 20:47

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.

• Nice answer, +1. Could you please help me by extending your answer for all (i.e., non-integer too) solutions. I request that if not give solution, then kindly give reference to look for. Jan 21, 2021 at 8:04
• @jiten Diophantine equations necessarily require the solutions to be integers. The solutions for all real numbers is trivial; it is simply a line. In algebra, all solutions are in the form $(x, \frac{c}{b} - \frac{a}{b} x)$, which can simply be derived from $ax + by = c$ => $by = c - ax$ => $y = \frac{c}{b} - \frac{a}{b} x$ May 20, 2023 at 2:48