Main Question for this Lesson
Given a linear Diophantine equation \(ax+by=c\), how can we find all integer solutions?
In the previous lesson, Linear Diophantine Equations Part 1, we began a discussion of linear Diophantine equations. In that lesson, we focused on what these equations are, when a solution exists, and how to find a solution when one exists. Recall, a linear Diophantine equation is an equation of the form \(ax+by=c\), where coefficients \(a\), \(b\), and \(c\) are all integers, and we’re looking for integers \(x\) and \(y\) that satisfy the equation.
In this lesson, we will explore how to find all solutions to linear Diophantine equations, and also look at finding solutions under various constraints.
Given a linear Diophantine equation \(ax+by=c\), how can we find all integer solutions?
Consider the following example, which was also discussed in the previous lesson.
A robot can move backwards or forwards with big steps (\(130\) cm) or small steps (\(50\) cm). In the previous lesson, we saw that if a robot takes \(2\) big steps forward and \(5\) small steps backward, it will end up \(10\) cm ahead of where it started.
Are there other moves that the robot can make to end up \(10\) cm ahead of where it started?
Solution:
In the previous lesson, we saw that we need to solve the equation \(130x + 50y = 10\), where \(x\) and \(y\) are integers. We also saw that one solution is \(x=2\) and \(y=-5\).
But there are many other solutions. Using guess and check, we find some other solutions:
\(x= -3\) and \(y = 8\), \(x = 7\) and \(y=-18\), \(x= -8\) and \(y =21\), \(\ldots\)
In fact, there are infinitely many integer solutions!
Do you notice a pattern appearing among these solutions?
Try picking two solutions, say \((x,y) = (2,-5)\) and \((x,y) = (-3,8)\). What is the difference between the two \(x\) values? What about the two \(y\) values?
Try all of the pairs. What do you notice?
First, when we say we are looking for the complete solution to an equation, we mean that we are looking for all solutions to the equation.
Let’s look closer at the linear Diophantine equation in Example \(1\): \[130x + 50y = 10\] Rearranging, we obtain \[50 y = -130x + 10\] And so, \[y = -\frac{13}{5}x + \frac{1}{5}\]
This is the equation of a line with slope \(-\frac{13}{5}\) and \(y\)-intercept \(\frac{1}{5}\).
Thus, the solutions to the linear Diophantine equation \(130x +50y = 10\) are exactly the points \((x,y)\) on this line whose coordinates are integers!
We know that \((2, -5)\) lies on this line. How can we find another point \((x,y)\) on this line with integer coordinates? Let’s look at what is happening geometrically.
The equation \(130x + 50 y = 10\) is the equation of a line through the point \((2, -5)\).
The slope of this line is equal to \(-\frac{130}{50}\), which can be reduced to \(-\frac{13}{5}\).
Notice that, in reducing this fraction, we factored out a common factor of \(10\), which is equal to \(\gcd(130, 50)\).
Now, from \((2, -5)\), how do we find another point on the line with integer coordinates?
We can move left \(5\) and up \(13\), to get to the point \((-3, 8)\).
Or, we can move right \(5\) and down \(13\), to get to the point \((7, -18)\).
From \((7, -18)\), we can again move right \(5\) and down \(13\), to get to the point \((12, -31)\).
We can continue in this manner to generate all of the points on the line with integer coordinates.
In general, every point \((x,y)\) that is of the form \(x = 2 + 5n\) and \(y = -5 - 13n\), where \(n\) is any integer will be a solution to the linear Diophantine equation \(130x + 50y =10\). Also, it turns out that every solution to this Diophantine equation must be of this form.
That is, the complete solution to the linear Diophantine equation \(130x + 50y = 10\) is
\(x = 2 + 5n\) and \(y = -5 - 13n\), where \(n\) is any integer.
Suppose that \(x=x_0\), \(y=y_0\) is one integer solution to the linear Diophantine equation \(ax+by=c\), and let \(d=\gcd(a,b)\).
Then, the complete solution is given by
\[x = x_0 + n\left(\frac{b}{d}\right), \quad y = y_0 - n\left(\frac{a}{d}\right)\] where \(n\) is any integer.
Let’s check this for the robot example. Here, we looking to find the complete solution to the linear Diophantine equation \(130x + 50y = 10\), so \(a=130\), \(b=50\), and \(c=10\). Also, \(d = \gcd(a,b) = \gcd(130, 50) = 10\). We had found that one solution is \((x_0, y_0) = (2, -5)\).
According to this theorem, the complete solution to the linear Diophantine equation \(130x + 50y = 10\) is \[x = x_0 + n\left(\frac{b}{d}\right), \quad y = y_0 - n\left(\frac{a}{d}\right)\] Substituting \(x_0 =2\), \(y_0 = -5\), \(a=130\), \(b= 50\), and \(d=10\): \[x = 2 + n\left(\frac{50}{10}\right), \quad y = -5 - n\left(\frac{130}{10}\right)\] This simplifies to \(x = 2 + 5n\), \(y = -5 - 13n\), where \(n\) is any integer.
As expected, this is exactly we had found earlier!
If we had started with the solution \((7, -18)\), we would have found that the complete solution to the linear Diophantine equation \(130x + 50y=10\) is
\[x = 7 + 5n, \quad y = -18 - 13n, \quad \text{where $n$ is any integer}\]
Can you convince yourself that this is the same solution set as we had found starting with the solution \((2, -5)\)?
First, find a solution \((x_0, y_0)\) to \(ax+by = c\). You can do so by inspection, or by using the techniques that we learned in the previous lesson.
The complete solution to the linear Diophantine equation is then \[x = x_0 +n\left(\frac{b}{d}\right), \quad y = y_0 -n\left(\frac{a}{d}\right), \text{where $n$ is any integer}\]
Determine the complete solution to the linear Diophantine equation \(2491x + 2173y = 159\).
Solution:
To determine the complete solution, we first need to find one solution. We will use the techniques we learned in the previous lesson to first find one solution.
We begin by calculating \(\gcd(2491, 2173)\) using the Euclidean Algorithm. \[\begin{align*} 2491&=2173\cdot 1+318, \text{ so }\gcd(2491, 2173)=\gcd(2173, 318)\tag{1}\\ 2173&=318\cdot 6+265, \text{ so } \gcd(2173, 318)=\gcd(318,265\tag{2})\\ 318&=265\cdot 1+53,\text{ so }\gcd(318, 265)=\gcd(265, 53)\tag{3}\\ 265&=53\cdot 5+0,\text{ so }\gcd(265, 53)=53\tag{4}\end{align*}\] Thus, \(\gcd(2173, 2491) = 53\).
Since \(159 = 3\times 53\), we know that there is a solution to the given linear Diophantine equation.
To find a solution, we work backwards through the steps above.
From line \((3)\), we have \[53 = 318 - 1\cdot 265\] Substituting for \(265\) using \((2)\): \[53 = 318 - 1(2173 - 6\cdot 318)\] Simplifying: \[53= 7\cdot 318 - 1\cdot2173\]
Substituting for \(318\) using \((1)\): \[53= 7(2491 - 1\cdot2173) - 1\cdot2173\] Simplifying: \[53= 7(2491) - 8(2173)\] Therefore, we can see that \(2491(7) + 2173(-8) = 53\).
Multiplying both sides of this equation by \(3\), we obtain: \[\begin{align*} 3[2491(7) + 2173(-8)] &= 3(53)\\ 2491(3\times7) + 2173(3\times(-8)) &= 159\\ 2491(21) + 2173(-24) &= 159\end{align*}\] Thus, a solution to the linear Diophantine equation \(2491x + 2173y = 159\) is \(x=21, y=-24\).
To determine the complete solution, we calculate: \[x = 21+ n\left(\frac{b}{d}\right), \quad y = -24 - n\left(\frac{a}{d}\right)\] Substituting \(a=2491\), \(b=2173\), and \(d=53\): \[x = 21 + n\left(\frac{2173}{53}\right), \quad y = -24 - n\left(\frac{2491}{53}\right)\] This simplifies to \(x = 21 + 41n\), \(y = -24 - 47n\).
Thus, the complete solution to the linear Diophantine equation \(2491x + 2173y = 159\) is
\(x = 21 + 41n\), \(y = -24 - 47n\), where \(n\) is any integer.
Notice that in order to find the complete solution to a linear Diophantine equation, we need to start with a solution, but it does not matter how we find this solution! If we can find a solution by inspection, trial-and-error, or some other method, this will also suffice! If we can find a solution quickly by inspection or trial-and-error, this can lead to quickly finding the complete solution, as we’ll see in our next example.
Determine the complete solution to the linear Diophantine equation \(15x - 24y = 9\).
Solution:
To determine the complete solution, we first need to find one solution. To do so, we could use the techniques we learned in the previous lesson, as we did in Example 2; however, if we can spot a solution by inspection, this can also be used to generate the complete solution!
By inspection, we can see that \(x=-1\), \(y=-1\) is a solution to this linear Diophantine equation. Thus, we can use \(x_0=-1\), \(y_0=-1\) to generate the complete solution.
That is, the complete solution is \[x = -1+ n\left(\frac{b}{d}\right), \quad y = -1 - n\left(\frac{a}{d}\right)\] Substituting \(a=15\), \(b=-24\), and \(d=\gcd(15, -24) = 3\): \[x = -1 + n\left(\frac{-24}{3}\right), \quad y = -1 - n\left(\frac{15}{3}\right)\] This simplifies to \(x = -1 -8n\), \(y = -1 - 5n\).
Thus, the complete solution to the linear Diophantine equation \(15x - 24y = 9\) is
\(x = -1 -8n\), \(y = -1 - 5n\), where \(n\) is any integer.
Determine the complete solution to the linear Diophantine equation \(8x + 9y = 3\).
To determine the complete solution, we first need to find one solution.
By inspection, we can see that \(x=-3\), \(y=3\) is a solution to this linear Diophantine equation. Thus, we can use \(x_0=-3\), \(y_0=3\) to generate the complete solution.
That is, the complete solution is \[x = -3+ n\left(\frac{b}{d}\right), \quad y = 3 - n\left(\frac{a}{d}\right)\] Substituting \(a=8\), \(b=9\), and \(d=\gcd(8, 9) = 1\): \[x = -3 + n\left(\frac{9}{1}\right), \quad y = 3 - n\left(\frac{8}{1}\right)\] This simplifies to \(x = -3 +9n\), \(y = 3 - 8n\).
Thus, the complete solution to the linear Diophantine equation \(8x +9y = 3\) is
\(x = -3 +9n\), \(y = 3-8n\), where \(n\) is any integer.
Determine the complete solution to the linear Diophantine equation \(4182x + 3689y = 102\).
To determine the complete solution, we first need to find one solution. We will use the techniques we learned in the previous lesson to first find one solution.
We begin by calculating \(\gcd(4182, 3689)\) using the Euclidean Algorithm. \[\begin{align*} 4182&=3689\cdot 1+493, \text{ so }\gcd(4182, 3689)=\gcd(3689, 493)\\ 3689&=493\cdot 7+238, \text{ so } \gcd(3689, 493)=\gcd(493,238)\\ 493&=238\cdot 2+17,\text{ so }\gcd(493, 238)=\gcd(238, 17)\\ 238&=17\cdot 14+0,\text{ so }\gcd(238, 17)=17\end{align*}\] Thus, \(\gcd(4182, 3689) = 17\).
Since \(102 = 6\times 17\), we know that there is a solution to the given linear Diophantine equation.
To find a solution, we work backwards through the steps above.
From line \((3)\), we have \[17 = 493 - 2\cdot 238\] Substituting for \(238\) using \((2)\): \[17 = 493 - 2(3689 - 7\cdot 493)\] Simplifying: \[17= 15\cdot 493 - 2\cdot3689\]
Substituting for \(493\) using \((1)\): \[17= 15(4182 - 1\cdot3689) - 2\cdot3689\] Simplifying: \[17= 15(4182) - 17(3689)\] Therefore, we can see that \(4182(15) + 3689(-17) = 17\).
Multiplying both sides of this equation by \(6\), we obtain: \[\begin{align*} 6[4182(15) + 3689(-17)] &= 6(17)\\ 4182(6\times15) + 3689(6\times(-17)) &= 102\\ 4182(90) + 3689(-102) &= 102\end{align*}\] Thus, a solution to the linear Diophantine equation \(4182x + 3689y = 102\) is \(x=90\), \(y=-102\).
To determine the complete solution, we calculate: \[x = 90+ n\left(\frac{b}{d}\right), \quad y = -102 - n\left(\frac{a}{d}\right)\] Substituting \(a=4182\), \(b=3689\), and \(d=17\): \[x = 90 + n\left(\frac{3689}{17}\right), \quad y = -102 - n\left(\frac{4182}{17}\right)\] This simplifies to \(x = 90 + 217n\), \(y = -102 - 246n\).
Thus, the complete solution to the linear Diophantine equation \(4182x + 3689y = 102\) is
\(x = 90 + 217n\), \(y = -102 - 246n\), where \(n\) is any integer.
Notice that what we have seen so far tells us that if a linear Diophantine equation has a solution, then it has infinitely many (since there are infinitely many choices for the integer \(n\)). But do all of these solutions make sense in the context of our problem? Consider the following example, which was also discussed in the previous lesson.
Sara needs \(\$2.15\) to buy a large coffee. She only has quarters and dimes, and the cashier insists that she pay with exact change. Is there a combination of quarters and dimes that will total \(\$2.15\)?
Solution:
We need to solve the equation \(25x +10y = 215\), where \(x\) and \(y\) are integers.
In Question \(5\) of the problem set from the previous lesson, we explored solving this linear Diophantine equation using the Euclidean algorithm, and found that a solution is \(x=43\) and \(y=-86\).
The answer suggests that we should use \(43\) quarters and \(-86\) dimes to total \(\$2.15\), which does not make sense in the context of this problem!
In Example \(4\), we really want is a solution where both \(x\) and \(y\) are non-negative integers (that is, integers greater than or equal to \(0\)).
First, what is the complete solution to this problem? In this problem \(a=25\), \(b=10\), and \(d=\gcd(a,b) = \gcd(25,10) = 5\). We also know that \(x=43\), \(y = -86\) is one solution to the linear Diophantine equation. Thus, we can use \(x_0=43\), \(y_0=-86\) to generate the complete solution.
That is, the complete solution is \[x = 43+ n\left(\frac{b}{d}\right), \quad y = -86 - n\left(\frac{a}{d}\right)\] Substituting \(a=25\), \(b=10\), and \(d=5\): \[x = 43+ n\left(\frac{10}{5}\right), \quad y = -86 - n\left(\frac{25}{5}\right)\] This simplifies to \(x = 43 +2n\), \(y = -86 - 5n\).
For the solution to make sense in the context of the problem, we need both \(x\geq 0\) and \(y\geq 0\). Which values of \(n\) will satisfy these conditions?
\[\begin{align*} x\geq 0 &\implies 43 + 2n \geq 0\\ &\implies 2n\geq -43\\ &\implies n \geq -21.5\end{align*}\] So \(n\) is an integer and \(n\geq -21.5\), which tells us that \(n\geq -21\).
Similarly, \[\begin{align*} y\geq 0 &\implies -86 - 5n \geq 0\\ &\implies -5n\geq 86\\ &\implies n \leq -17.2\end{align*}\] So \(n\) is an integer and \(n\leq -17.2\), which tells us that \(n\leq -18\).
Solving for \(n\) in an inequality is similar to solving for \(n\) in an equation. However, we must reverse the inequality sign when multiplying or dividing by a negative number.
That is, if \(a\leq b\) then \(-a \geq-b\).
Thus, in order for there to be a non-negative number of quarters and dimes, we must have \(n\geq -21\) and also have \(n\leq -18\). Thus, there are \(4\) possible values for \(n\): \(-18, -19, -20, -21\).
Using \(x = 43 +2n\) and \(y = -86 - 5n\), we find there are four solutions to this problem, given the context. They are:
\(x=7\), \(y=4\) (when \(n=-18\))
\(x=5\), \(y=9\) (when \(n=-19\))
\(x=3\), \(y=14\) (when \(n=-20\))
\(x=1\), \(y=19\) (when \(n=-21\))
Determine all solutions to the linear Diophantine equation \(15x-24y=9\) with \(0\leq x\leq 30\) and \(0\leq y \leq 30\).
Solution:
From Example \(3\), we know that the complete solution to this linear Diophantine equation is \(x = -1 -8n\), \(y = -1 - 5n\), where \(n\) is any integer. There are four restrictions to consider: \[\begin{align*} x\geq 0 &\implies -1- 8n \geq 0\\ &\implies -8n\geq 1\\ &\implies n \leq -0.125\end{align*}\] So \(n\) is an integer and \(n\leq -0.125\), which tells us that \(n\leq -1\). \[\begin{align*} y\geq 0 &\implies -1 - 5n \geq 0\\ &\implies -5n\geq 1\\ &\implies n \leq -0.2\end{align*}\] So \(n\) is an integer and \(n\leq -0.2\), which tells us that \(n\leq -1\). \[\begin{align*} x\leq 30 &\implies -1- 8n \leq 30\\ &\implies -8n\leq 31\\ &\implies n \geq -3.875\end{align*}\] So \(n\) is an integer and \(n\geq -3.875\), which tells us that \(n\geq -3\). \[\begin{align*} y\leq 30 &\implies -1 - 5n \leq 30\\ &\implies -5n\leq 31\\ &\implies n \geq -6.2\end{align*}\] So \(n\) is an integer and \(n\geq -6.2\), which tells us that \(n\geq -6\).
Therefore, to have \(0\leq x \leq 30\) and \(0\leq y \leq 30\), it must be the case that \(n\leq -1\) and \(n\geq -3\) and \(n\geq -6\). The only values of \(n\) that satisfy all three of these conditions are \(n=-1, -2, -3\).
Substituting in each value of \(n\), we find that the solutions are
\(x=7\) and \(y=4\) (\(n=-1\)), \(x=15\) and \(y=9\) (\(n=-2\)), \(x=23\) and \(y=14\) (\(n=-3\))