Main Question for this Lesson
Given three integers \(a\), \(b\), and \(c\), how can we find a solution to \(ax+by=c\), where \(x\) and \(y\) are integers?
In this lesson (and the next), we will explore linear Diophantine equations. For this lesson, we will focus on what these equations are, when a solution exists, and how to find a solution when one exists. In the lesson two weeks from now, we will explore how to find all solutions to linear Diophantine equations, and also look at finding solutions under various constraints.
A Diophantine equation, named after Diophantus of Alexandria, is a polynomial equation with integer coefficients that is intended to be solved with integer solutions.
One Diophantine equation you’ve likely seen is \[x^2 + y^2 = z^2\] Positive integer solutions to this Diophantine equation (for example, \(x=3\), \(y=4\), \(z=5\)) correspond to right-angled triangles with integer side lengths.
Another famous Diophantine equation is \[x^n + y^n = z^n\] where \(n\) is an integer \(\geq 3\). It has been shown that this Diophantine equation has no solution where \(x\), \(y\), and \(z\) are positive integers. This was first stated by the mathematician Fermat in the 1600s, but was not proven until 1994 by the mathematician Andrew Wiles.
In this lesson, we’re going to focus on linear Diophantine equations. A (two-variable) linear Diophantine equation is an equation of the form \[ax + by = c\] where \(a\), \(b\), and \(c\) are given integers and we are interested in solving for integers \(x\) and \(y\).
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. Since \(x\) and \(y\) represent the number of quarters and dimes, respectively, that Sara uses, notice that it makes sense that we are only interested in integer solutions to this equation. Further, we should also ensure that \(x\) and \(y\) are not negative.
By using systematic guess and check, we can come up with the following possible solutions:
\(x=1\) and \(y=19\), or \(x=3\) and \(y=14\), or \(x=5\) and \(y=9\), or \(x=7\) and \(y=4\)
There are no other solutions. Can you see why?
A robot can move backwards or forwards with big steps (\(130\) cm) or small steps (\(50\) cm). Is there a series of moves that the robot can make to end up \(10\) cm ahead of where it started?
Solution:
We need to solve the equation \(130x + 50y = 10\), where \(x\) and \(y\) are integers.
Using guess and check, we find one (of many) solutions to be \(x=2\) and \(y=-5\). That is, if the robot takes \(2\) big steps forward and \(5\) small steps backward, it will end up \(10\) cm ahead of where it started.
There are many other solutions. Can you find another solution?
It is not always easy to find a solution to a linear Diophantine equation by trial-and-error.
For example, trial-and-error could be time consuming if we used that technique to find integers \(x\) and \(y\) that satisfy the linear Diophantine equation \[1053x+481y=13\]
Given three integers \(a\), \(b\), and \(c\), how can we find a solution to \(ax+by=c\), where \(x\) and \(y\) are integers?
Be careful! There may not be an integer solution! In this lesson, we will determine conditions on \(a\), \(b\), and \(c\) that guarantee an integer solution to the equation \(ax+by=c\), and learn a method for finding such a solution, in the case where one exists.
Consider the linear Diophantine equation \[3x+6y=5\] If we divide both sides by \(3\), the equation becomes \[x + 2y = \frac{5}{3}\]
Before reading further, can you see a problem with it being true that \(x + 2y = \frac{5}{3}\)?
Since we are told \(3x+6y=5\) is a linear Diophantine equation, a solution must have both \(x\) and \(y\) being integers. If \(x\) and \(y\) are both integers, \(x+2y\) must also be an integer, but \(\frac{5}{3}\) is not an integer! Therefore, the equation \(3x+6y=5\) cannot have any integer solutions.
In general, we have the following result:
If \(d\) is an integer that divides both \(a\) and \(b\), but \(d\) does not divide \(c\), then the linear Diophantine equation \[ax+by = c\] has no solutions.
Does the linear Diophantine equation \(14x + 35 y = 4\) have a solution?
Since \(7\) divides \(14\) and \(35\), but does not divide \(4\), this linear Diophantine equation has no solution.
If we’re going to discuss whether or not we can solve the linear Diophantine equation \(ax+by=c\) for integers \(x\) and \(y\), it appears as though we’ll need to investigate common divisors of \(a\) and \(b\).
Suppose \(a\) and \(b\) are integers. If \(d\) is an integer that divides both \(a\) and \(b\), we call \(d\) a common divisor of \(a\) and \(b\). The largest integer that divides both \(a\) and \(b\) is called the greatest common divisor of \(a\) and \(b\), denoted \(\gcd(a,b)\).
What is \(\gcd(48,32)\)?
Solution:
Let’s list the positive divisors of each.
Positive divisors of \(48\): \(1\), \(2\), \(3\), \(4\), \(6\), \(8\), \(12\), \(16\), \(24\), \(48\)
Positive divisors of \(32\): \(1\), \(2\), \(4\), \(8\), \(16\), \(32\)
Since the largest divisor that they have in common is \(16\), \(\gcd(48,32) = 16\).
Finding \(\gcd(a,b)\) by factoring \(a\) and \(b\) may be very time consuming if \(a\) and \(b\) are large.
For example, try to calculate \(\gcd(3551, 4399)\) or \(\gcd(104\,723, 103\,093)\) by factoring.
Instead, we will use a method that does not require us to find a single divisor of \(a\) or \(b\). The first step is the division algorithm.
Let \(a\) and \(b\) be integers with \(b>0\). There are unique integers \(q\) (the quotient) and \(r\) (the remainder) such that \[a = bq + r \quad \text{and} \quad 0\leq r <b\]
For example, suppose \(a=15\) and \(b=6\). We can write \(15 = 6\cdot2+3\), so \(q=2\) and \(r=3\). Notice that it is also true that \(15=6\cdot1 + 9\) and \(15 = 6\cdot3 + (-3)\); however, neither \(9\) nor \(-3\) satisfy the requirement that they are \(\geq 0\) and also \(<b\). So, it turns out that \(q=2\) and \(r=3\) are the unique \(q\) and \(r\) satisfying the division algorithm when \(a=15\) and \(b=6\).
For \(a\) and \(b\), calculate \(q\) and \(r\) from the division algorithm.
\(a=30\), \(b=6\)
\(a=9\), \(b=6\)
\(a=-2\), \(b=6\)
Solution:
\(30 = 6\cdot5+0\), so \(q=5\), \(r=0\).
\(9 = 6\cdot1+3\), so \(q=1\), \(r=3\).
\(-2 = 6\cdot(-1)+4\), so \(q=-1\), \(r=4\).
Now that we know how to find \(q\) and \(r\) in the division algorithm, we are ready to learn an important fact that will help us calculate greatest common divisors more efficiently.
If \(a = bq + r\), then \(\gcd(a,b) = \gcd(b,r)\).
As we saw above, when \(a=15\) and \(b=6\), we have \(q=2\) and \(r=3\). Notice that \(\gcd(15,6) = 3\) and \(\gcd(6,3)=3\). So the important fact holds, since \(\gcd(15,6) = \gcd(6,3)\).
Similarly, in Example \(4\), we saw that when \(a=30\) and \(b=6\), we have \(q=5\) and \(r=0\). Notice that \(\gcd(30,6) = 6\) and \(\gcd(6,0)=6\). So the important fact holds, since \(\gcd(30,6) = \gcd(6,0)\). Note that \(\gcd(a,0) =a\) for any positive integer \(a\), since \(0\) is divisible by every positive integer.
For \(a\) and \(b\), verify that the important fact holds.
\(a=9\), \(b=6\)
\(a=-2\), \(b=6\)
We saw in Example \(4\) that \(9 = 6\cdot1+3\). Thus, \(q = 1\) and \(r=3\). Notice that \(\gcd(9, 6) = 3\) and \(\gcd(6,3)=3\). Since \(\gcd(a,b) = \gcd(b,r)\), the important fact holds.
We saw in Example \(4\) that \(-2 = 6\cdot(-1)+4\). Thus, \(q=-1\) and \(r=4\). Notice that \(\gcd(-2,6) = 2\) and \(\gcd(6,4)=2\). Since \(\gcd(a,b) = \gcd(b,r)\), the important fact holds.
How can we use the important fact to calculate greatest common divisors more efficiently? We will iterate the division algorithm and apply the important fact each time.
Calculate \(\gcd(117, 55)\).
Solution:
Since \(117=55\cdot2+7\), we have
\(q = 2\) and \(r = 7\) from the division algorithm. Thus,
by the important fact, we know \(\gcd(117, 55)
= \gcd(55, 7)\).
Now, let’s repeat this process on \(55\) and \(7\).
Since, \(55=7\cdot7+6\), we have \(q=7\) and \(r=6\) from the division algorithm. Thus, by
the important fact, we know \(\gcd(55, 7) =
\gcd(7, 6)\).
Now, let’s repeat this process on \(7\)
and \(6\).
Since, \(7=6\cdot1+1\), we have \(q=1\) and \(r=1\) from the division algorithm. Thus, by
the important fact, we know \(\gcd(7, 6) =
\gcd(6, 1)\).
Thus, we can conclude that \(\gcd(117, 55) = \gcd(55,7) = \gcd(7,6) = \gcd(6,1) = 1.\)
This method of repeatedly using the division algorithm along with the important fact to find the greatest common divisor of two integers is called the Euclidean algorithm.
Input: Positive integers \(a\) and \(b\).
Step 1: Arrange \(a\) and \(b\) so that \(a\geq b\).
Step 2: Write \(a=bq+r\), with \(0\leq r<b\).
Step 3: If \(r=0\), then stop! If \(r>0\), then go back to Step \(1\), this time with the pair \((b,r)\).
Step 4: The last non-zero remainder \(r\) if such an \(r\) exists, or else output \(b\).
The greatest common divisor of the two integers will be equal to the last non-zero remainder that is seen in the Euclidean algorithm. When working through this algorithm, we will use the fact that \(\gcd(a,0) =a\), for any positive integer \(a\).
Let’s work through another example to convince ourselves that this algorithm will always output \(\gcd(a,b)\).
Calculate \(\gcd(481, 1053)\) using the Euclidean algorithm.
Solution:
Here we will apply the Euclidean algorithm to the pair \((481, 1053)\). We will keep track of what is happening with the gcd on the right-hand side.
| Euclidean Algorithm Step | GCD Equality |
|---|---|
| As \(481 < 1053\), set \(a = {\color{blue}1053}\) and \(b={\color{blue}481}\) | \(\gcd(481, 1053) = \gcd(1053, 481)\) |
| Write \({\color{blue}1053} = {\color{blue}481}\cdot 2 + 91\) (\(r=91\)) | \(\gcd(1053, 481) = \gcd(481, 91)\) |
| Write \({\color{blue}481} = {\color{blue}91}\cdot 5+ 26\) (\(r=26\)) | \(\gcd(481, 91) = \gcd(91,26)\) |
| Write \({\color{blue}91} = {\color{blue}26}\cdot 3 + 13\) (\(r=13\)) | \(\gcd(91,26) = \gcd(26,13)\) |
| Write \({\color{blue}26} = {\color{blue}13} \cdot 2+ 0\) (\(r=0\)) | \(\gcd(26,13) =\gcd(13,0)=13\) |
From the gcd equalities on the right hand side, we see that \(\gcd(481, 1053) = \gcd(13,0) = 13\).
Since \(r < b\), the integers get smaller after each iteration of the division algorithm, and so this procedure must eventually stop. Can you convince yourself that you will always reach a remainder of zero, and that the output will always be \(\gcd(a,b)\)?
Calculate \(\gcd(427, 616)\) using the Euclidean algorithm.
| As \(427 < 616\), set \(a = {\color{blue}616}\) and \(b={\color{blue}427}\) | \(\gcd(427, 616) = \gcd(616, 427)\) |
| Write \({\color{blue}616} = {\color{blue}427}\cdot 1 + 189\) (\(r=189\)) | \(\gcd(616, 427) = \gcd(427, 189)\) |
| Write \({\color{blue}427} = {\color{blue}189}\cdot 2+ 49\) (\(r=49\)) | \(\gcd(427, 189) = \gcd(189,49)\) |
| Write \({\color{blue}189} = {\color{blue}49}\cdot 3 + 42\) (\(r=42\)) | \(\gcd(189,49) = \gcd(49,42)\) |
| Write \({\color{blue}49} = {\color{blue}42} \cdot 1+ 7\) (\(r=7\)) | \(\gcd(49,42) =\gcd(42,7)\) |
| Write \({\color{blue}42} = {\color{blue}7} \cdot 6+ 0\) (\(r=0\)) | \(\gcd(42,7) =\gcd(7,0)=7\) |
From the gcd equalities on the right hand side we see that \(\gcd(427, 616) = \gcd(7,0) = 7\).
As we’ll see in our next example, the Euclidean algorithm not only finds \(\gcd(a,b)\), but by working backwards, we can actually use it to solve linear Diophantine equations!
Find integers \(x\) and \(y\) such that \(1053x + 481 y = 13\).
Solution:
As we saw in Example \(6\), the Euclidean algorithm gives \[\begin{align*} 1053&=481\cdot2+91\tag{1}\\ 481&=91\cdot 5+26\tag{2}\\ 91&=26\cdot3+13\tag{3}\\ 26&=13\cdot2+0\tag{4}\end{align*}\] And so \(\gcd(1053,481)=13\). Notice that this is the value of \(c\) in the equation. We can exploit this fact by tracing our steps in the Euclidean algorithm and working backwards as follows:
From \((3)\): \[13 = \underline{91} - 3\cdot \underline{26}\] Substituting for \(26\) using \((2)\): \[13 = \underline{91} - 3(\underline{481} - 5\cdot \underline{91})\] Simplifying: \[13 = 16\cdot \underline{91} - 3\cdot\underline{481}\] Substituting for \(91\) using \((1)\): \[13 = 16(\underline{1053} - 2(\underline{481})) - 3\cdot\underline{481}\] Simplifying: \[13= 16(\underline{1053}) - 35(\underline{481})\] That is, \(1053(16) + 481(-35) = 13\). Therefore, one solution is \(x=16\), \(y=-35\). Check!
Find integers \(x\) and \(y\) such that \(427x + 616y = 7\).
From Exercise \(3\), the Euclidean algorithm gives \[\begin{align*} 616&=427\cdot 1 + 189\\ 427&=189\cdot 2+ 49\\ 189&=49\cdot 3 + 42\\ 49&=42\cdot 1+ 7\\ 42&= 7\cdot 6+ 0\end{align*}\] And so we have \(\gcd(616,427)=7\). Notice that this is our value of \(c\) in the equation. Working backwards, from equation \((4)\) we have: \[7 = \underline{49} - 1\cdot \underline{42}\] Substituting for \(42\) using \((3)\): \[7 = \underline{49} - 1(\underline{189}- 3\cdot \underline{49})\] Simplifying: \[7 = 4\cdot \underline{49} - 1\cdot\underline{189}\] Substituting for \(49\) using \((2)\): \[7 = 4\cdot(\underline{427}-2\cdot\underline{189}) - 1\cdot\underline{189}\] Simplifying: \[7= 4(\underline{427}) - 9(\underline{189})\] Substituting for \(189\) using \((1)\): \[7= 4(\underline{427}) - 9(\underline{616}-1\cdot\underline{427})\] Simplifying: \[7= 13(\underline{427}) - 9(\underline{616})\] That is, \(427(13) + 616(-9) = 7\). Therefore, one solution is \(x=13\), \(y=-9\). Check!
We now have a strategy to find integers \(x\) and \(y\) such that \(ax+by = c\) when \(c=\gcd(a,b)\): We can work backwards through our steps in the Euclidean algorithm, starting with the line where \(r=\gcd(a,b)\), as we saw in Example \(7\). But what if we need to solve \(ax+by = c\), where \(c\) is not equal to \(\gcd(a,b)\)?
Find integers \(x\) and \(y\) such that \(1053x + 481 y = 39\).
Solution:
Notice that \(39 = 3\times 13\). From the Example \(7\), we know that \(1053(16) + 481(-35) = 13\).
Multiplying the entire equation by \(3\) gives \[\begin{align*} 3\left(1053(16) + 481(-35)\right) &= 3(13)\\ 3\left(1053(16)\right) + 3\left(481(-35)\right) &= 3(13)\\ 1053(3\cdot16) + 481(3\cdot(-35)) &= 39\\ 1053(48) + 481(-105) &= 39\end{align*}\] Thus, there is a solution, namely \(x=48\), \(y=-105\). Check!
From Example \(8\), we can see that if \(\gcd(a,b)\) divides \(c\), then we can use a solution to \(ax+by = \gcd(a,b)\) to find a solution to the equation \(ax+by = c\). What if \(\gcd(a,b)\) does not divide \(c\)?
Find integers \(x\) and \(y\) such that \(1053x + 481 y = 50\).
Solution:
Suppose that integers \(x\) and \(y\) that satisfy the above equation. Since \(13 = \gcd(1053, 481)\), we can factor \(13\) out of the left hand side of the equation: \[\begin{align*} 1053x + 481 y &= 50\\ (13\cdot81)x + (13\cdot 37)y &= 50\\ 13\left(81x+37y\right) &= 50\\ 81x+37y &= \frac{50}{13}\end{align*}\] But since \(x\) and \(y\) are integers, this last equality is impossible!
Therefore, there is no solution to the linear Diophantine equation \(1053x + 481 y = 50\).
From Example \(9\), we can see that if \(\gcd(a,b)\) does not divide \(c\), then the equation \(ax+by = c\) does not have a solution where \(x\) and \(y\) are integers.
The following theorem summarizes what we have observed about solutions to linear Diophantine equations.
The linear Diophantine equation \[ax+by = c\] has a solution if and only if \(\gcd(a,b)\) divides \(c\).
Using the Euclidean algorithm and working backwards, we can find integers \(x\) and \(y\) such that \[ax+by = \gcd(a,b)\]
Once we have found \(x\) and \(y\) such that \(ax+by = \gcd(a,b)\), we can multiply this solution by \(\dfrac{c}{\gcd(a,b)}\) to get a solution to \(ax+by = c\).
Find integers \(x\) and \(y\) such that \(427x + 616y = 91\).
From Exercise \(3\), we know that \(\gcd(427,616)=7\). Since \(91 = 13\times 7\), we know \(7\) divides \(91\) and so this linear Diophantine equation has a solution.
From Exercise \(4\), we know that \[427(13) + 616(-9) = 7\] and so multiplying the entire equation by \(13\) gives \[\begin{align*} 13\left(427(13) + 616(-9)\right) &= 13(7)\\ 13\left(427(13)\right) + 13\left(616(-9)\right) &= 13(7)\\ 427(13\cdot13) + 616(13\cdot(-9)) &= 91\\ 427(169) + 616(-117) &= 91\end{align*}\] Thus, \(x=169\), \(y=-117\) is a solution. Check!
Find integers \(x\) and \(y\) such that \(427x + 616y = 101\).
Since \(\gcd(427,616) = 7\), and \(7\) does not divide \(101\), there is no solution to this linear Diophantine equation.