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.
As indicated above, we are only interested in integer solutions to the equation . So by a solution to , we mean a pair of integers 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 , where , and are integers, the first step is to find the greatest common divisor of and , using Euclidean algorithm. We use the notation to denote the greatest common divisor. Once we know , we would know whether the equation 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 . 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 , 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 . The equation 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, . We can trace back the steps in finding the GCD to see that
Thus the pair and is a solution to the equation . Based on this development, we can see that always has a solution as long as is a multiple of . For example, the equation has solutions since we have the following:
Thus the pair and is a solution to the equation , which is the first linear Diophantine equation listed at the beginning of the post. We summarize this discussion in the following lemma.
Let . The linear Diophantine equation has a solution if and only if .
The notation means that is divisible by .
Proof of Lemma 1
The above discussion essentially shows the direction . The extended Euclidean algorithm indicates that has a solution and . If for some integer , then indicates that the pair and is a solution to .
The direction follows from the observation that always divides the left-hand side of . Thus must divide the right-hand side as well unless the equation has no solution.
It turns out that if we can find one solution to a linear Diophantine equation, we can find infinitely many solutions.
If the pair and is a solution to , then so is the following number pair
where is any integer.
We can prove Lemma 2 by plugging the new solutions into the equation . We can also observe that if we increase by the value of , we increase the left-hand side of the equation by . On the other hand, if we decrease by the amount , we decrease the left-hand side of the equation by . 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 .
and for all integers
But the above solution set is not complete. For example, the number pair and is also a solution to the equation , but is not listed above. The following theorem will give the complete solution set.
Let . If the pair and is a solution to , then the complete solution set of the equation consists of all the integer pairs such that
where is any integer.
Proof of Theorem 3
Suppose that the pair and is a solution to . 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
To see the second point, suppose that the number pair and is a solution to the equation . We have the following.
Rearranging and dividing by , we have the following.
Note that the two fractions in the last equation are integers since is the greatest common divisor of and . Furthermore . 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 divides . Because , the number cannot divide . So the number must divide . So for some integer , we have:
Plug into (1), we have . This leads to the following.
Equations (2) and (3) show that the solution and is of the form given in the theorem.
Based on Theorem 3, the complete solution set to the equation is the following:
where is any integer.
A linear Diophantine equation is solvable if and only if where .
If a linear Diophantine equation is solvable, solving it involves two steps.
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 , we can just work backward in the Euclidean algorithm to find a solution to the equation , which in terms leads to a solution to .
Theorem 3 provides a way to desribe the complete solution set of the linear Diophantine equation based on the particular solution that is found in Step 1.
To solve , we need to find the GCD of and (the negative sign of can be dropped). We use the Euclidean algorithm.
The GCD is , which divides . 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 . Then we multiply that solution by . Working backward, we get:
So the number pair and is a solution of . Thus the number pair and is a solution of . Thus the following completely describes the solution set of .
To solve , note that the GCD of and is , which does not divide . Thus the equation has no solutions.
To solve , first find the GCD of and . We apply the Euclidean algorithm.
Thus the GCD is 1. So the equation has solutions. To get one specific solution, we work backward from the above divisions and obtain:
Thus and is a specific solution to . The complete solution set is described by:
for any integer .