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}

Advertisements

One thought on “Solving Linear Diophantine Equations

  1. Pingback: How to Chinese remainder, part 1 | Exploring Number Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s