# Solving Linear Diophantine Equations

Equations such as the ones in the following list always have solutions in real numbers. When we focus only on integer solutions, they are called linear Diophantine equations. In this post, we discuss how to work with linear Diophantine equations in two unknowns. Specifically we show, given such an equation, how to tell if it has solutions and if it does have solutions, how to describe the complete solution set.

$1638x+357y=819$

$255x - 2261y = 1003$

$78x + 195y=45$

$374x+285y=49$

$21x+10y+25z=26$

$22x_1+15x_2+91x_3+437x_4=255$

As indicated above, we are only interested in integer solutions to the equation $ax+by=c$. So by a solution to $ax+by=c$, we mean a pair of integers $(x,y)$ that satisfies the equation.

Solving linear Diophantine equations is a topic that is an extension of the discussion on Euclidean algorithm and the extended Euclidean algorithm in this previous post.

Here’s the thought process. To solve the linear Diophantine equation $ax+by=c$, where $a$, $b$ and $c$ are integers, the first step is to find the greatest common divisor of $a$ and $b$, using Euclidean algorithm. We use the notation $\text{GCD}(a,b)$ to denote the greatest common divisor. Once we know $\text{GCD}(a,b)$, we would know whether the equation $ax+by=c$ has solutions. If it does have solutions, the same algorithm that derives the GCD will generate a particular solution of the equation (this is the extended Euclidean algorithm). From the particular solution, we can describe completely the solution set of the equation $ax+by=c$. In the next section, we discuss this thought process in greater details.

___________________________________________________________________________________________________________________

How to Find Solutions

We demonstrate the method using the linear Diophantine equation $1638x+357y=819$, the first one in the above list, proving any necessary lemma and theorem along the way. We work our way to Theorem 3 below, which gives a way to describe the complete solution set of any linear Diophantine equation (if it has one solution).

Let $d=\text{GCD}(a,b)$. The equation $ax+by=d$ always has a solution. In fact this statement is called the extended Euclidean algorithm. The solution can be obtained by working backward from the Euclidean algorithm (when we use it to obtain the GCD).

For example, $\text{GCD}(1638,357)=21$. We can trace back the steps in finding the GCD to see that

$1638 \cdot (-5)+357 \cdot 23=21$.

Thus the pair $x=-5$ and $y=23$ is a solution to the equation $1638x+357y=21$. Based on this development, we can see that $1638x+357y=c$ always has a solution as long as $c$ is a multiple of $21$. For example, the equation $1638x+357y=819$ has solutions since we have the following:

$1638 \cdot (-5 \cdot 39)+357 \cdot (23 \cdot 39)=21 \cdot 39=819$.

Thus the pair $x=-195$ and $y=897$ is a solution to the equation $1638x+357y=819$, which is the first linear Diophantine equation listed at the beginning of the post. We summarize this discussion in the following lemma.

Lemma 1

Let $d=\text{GCD}(a,b)$. The linear Diophantine equation $ax+by=c$ has a solution if and only if $d \ \lvert \ c$.

The notation $d \ \lvert \ c$ means that $c$ is divisible by $d$.

Proof of Lemma 1
The above discussion essentially shows the direction $\Longleftarrow$. The extended Euclidean algorithm indicates that $ax+by=d$ has a solution $x=x_0$ and $y=y_0$. If $c=d \cdot k$ for some integer $k$, then $a(x_0 \cdot k)+b(y_0 \cdot k)=d \cdot k$ indicates that the pair $x=x_0 \cdot k$ and $y=y_0 \cdot k$ is a solution to $ax+by=c$.

The direction $\Longrightarrow$ follows from the observation that $d=\text{GCD}(a,b)$ always divides the left-hand side of $ax+by=c$. Thus $d$ must divide the right-hand side as well unless the equation has no solution. $\blacksquare$

It turns out that if we can find one solution to a linear Diophantine equation, we can find infinitely many solutions.

Lemma 2

If the pair $x=x_0$ and $y=y_0$ is a solution to $ax+by=c$, then so is the following number pair

$x=x_0+b \cdot k$ and $y=y_0-a \cdot k$

where $k$ is any integer.

We can prove Lemma 2 by plugging the new solutions into the equation $ax+by=c$. We can also observe that if we increase $x$ by the value of $b$, we increase the left-hand side of the equation by $a \cdot b$. On the other hand, if we decrease $y$ by the amount $b$, we decrease the left-hand side of the equation by $b \cdot a$. The net effect is that the left-hand side of the equation remains unchanged.

Using Lemma 2, the following describes infinitely many solutions of the equation $1638x+357y=819$.

$x=-195+357k$ and $y=897-1638k$ for all integers $k$

But the above solution set is not complete. For example, the number pair $x=-178$ and $y=819$ is also a solution to the equation $1638x+357y=819$, but is not listed above. The following theorem will give the complete solution set.

Theorem 3

Let $d=\text{GCD}(a,b)$. If the pair $x=x_0$ and $y=y_0$ is a solution to $ax+by=c$, then the complete solution set of the equation consists of all the integer pairs $(x,y)$ such that

$\displaystyle x=x_0+\frac{b}{d} \cdot k$

$\displaystyle y=y_0-\frac{a}{d} \cdot k$

where $k$ is any integer.

Proof of Theorem 3

Suppose that the pair $x=x_0$ and $y=y_0$ is a solution to $ax+by=c$. Two points to show. One is that any number pair of the above form is a solution. The other is that any solution is of the above form. To see the first, note that

$\displaystyle a(x_0+\frac{b}{d} \cdot k)+b(y_0-\frac{a}{d} \cdot k)=ax_0+by_0=c$

To see the second point, suppose that the number pair $x=x_1$ and $y=y_1$ is a solution to the equation $ax+by=c$. We have the following.

$ax_0+by_0=c$

$ax_1+by_1=c$

Rearranging and dividing by $d$, we have the following.

$a(x_1-x_0)=b(y_0-y_1)$

$\displaystyle \frac{a}{d}(x_1-x_0)=\frac{b}{d}(y_0-y_1) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

Note that the two fractions in the last equation are integers since $d$ is the greatest common divisor of $a$ and $b$. Furthermore $\displaystyle \text{GCD} \biggl(\frac{a}{d},\frac{b}{d}\biggr)=1$. Note that after canceling out all the common prime factors of two numbers, the resulting two numbers should be relatively prime.

Based on equation (1) above, the number $\displaystyle \frac{b}{d}$ divides $\displaystyle \frac{a}{d}(x_1-x_0)$. Because $\displaystyle \text{GCD} \biggl(\frac{a}{d},\frac{b}{d}\biggr)=1$, the number $\displaystyle \frac{b}{d}$ cannot divide $\displaystyle \frac{a}{d}$. So the number $\displaystyle \frac{b}{d}$ must divide $\displaystyle x_1-x_0$. So for some integer $k$, we have:

$\displaystyle x_1-x_0=\frac{b}{d} \cdot k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

Plug $\displaystyle \frac{b}{d} \cdot k$ into (1), we have $\displaystyle \frac{a}{d} \cdot \frac{b}{d} \cdot k=\frac{b}{d}(y_0-y_1)$. This leads to the following.

$\displaystyle y_0-y_1=\frac{a}{d} \cdot k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

Equations (2) and (3) show that the solution $x=x_1$ and $y=y_1$ is of the form given in the theorem. $\blacksquare$

Based on Theorem 3, the complete solution set to the equation $1638x+357y=819$ is the following:

$\displaystyle x=-195+\frac{357}{21} \cdot k=-195+17k$

$\displaystyle y=897-\frac{1638}{21} \cdot k=897-78k$

where $k$ is any integer.

___________________________________________________________________________________________________________________

Recap

A linear Diophantine equation $ax+by=c$ is solvable if and only if $d \ \lvert \ c$ where $d=\text{GCD}(a,b)$.

If a linear Diophantine equation $ax+by=c$ is solvable, solving it involves two steps.

Step 1
We first find a particular solution. We can find one by trial and error if the numbers are not too large. Otherwise, we can apply the extended Euclidean algorithm. Note that if we use the Euclidean algorithm to find $d=\text{GCD}(a,b)$, we can just work backward in the Euclidean algorithm to find a solution to the equation $ax+by=d$, which in terms leads to a solution to $ax+by=c$.

Step 2
Theorem 3 provides a way to desribe the complete solution set of the linear Diophantine equation $ax+by=c$ based on the particular solution that is found in Step 1.

___________________________________________________________________________________________________________________

More Examples

To solve $255x - 2261y = 1003$, we need to find the GCD of $255$ and $2261$ (the negative sign of $2261$ can be dropped). We use the Euclidean algorithm.

$2261=8 \cdot 255+221$

$255=1 \cdot 221+34$

$221=6 \cdot 34+17$

$34=2 \cdot 17+0$

The GCD is $17$, which divides $1003$. So the equation has solutions. We need to find a specific solution. First we work backward from the above divisions to find a solution to $255x - 2261y = 17$. Then we multiply that solution by $59$. Working backward, we get:

$255(-62)-2261(-7)=17$

So the number pair $x=-62$ and $y=-7$ is a solution of $255x - 2261y = 17$. Thus the number pair $x=-62 \cdot 59=-3658$ and $y=-7 \cdot 59=-413$ is a solution of $255x - 2261y = 1003$. Thus the following completely describes the solution set of $85x - 68y = 51$.

$\displaystyle x=-3658-\frac{2261}{17} \cdot k=-3658-133k$

$\displaystyle y=-413-\frac{255}{17} \cdot k=-413-15k$

________________________________

To solve $78x+195y=45$, note that the GCD of $78$ and $195$ is $39$, which does not divide $45$. Thus the equation has no solutions.

________________________________

To solve $374x+285y=49$, first find the GCD of $374$ and $285$. We apply the Euclidean algorithm.

$374=1 \cdot 285+89$

$285=3 \cdot 89+18$

$89=4 \cdot 18+17$

$18=1 \cdot 17+1$

$17=17 \cdot 1+0$

Thus the GCD is 1. So the equation has solutions. To get one specific solution, we work backward from the above divisions and obtain:

$374(-16)+285(21)=1$

Thus $x=-16 \cdot 49=-784$ and $y=21 \cdot 49=1029$ is a specific solution to $374x+285y=49$. The complete solution set is described by:

$x=-784+285k$

$y=1029-374k$

for any integer $k$.

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$