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.
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.
Calculate \(\gcd(427, 616)\) using the Euclidean algorithm.
| Euclidean Algorithm Steps | GCD Equality |
|---|---|
| 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\).
Find integers \(x\) and \(y\) such that \(427x + 616y = 7\).
From Exercise \(3\), the Euclidean algorithm gives \[\begin{align*} 616&=427\cdot 1 + 189\tag{1}\\ 427&=189\cdot 2+ 49\tag{2}\\ 189&=49\cdot 3 + 42\tag{3}\\ 49&=42\cdot 1+ 7\tag{4}\\ 42&= 7\cdot 6+ 0\tag{5}\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!
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.
Calculate the following gcds using the Euclidean algorithm.
\(\gcd(12, 57)\)
\(\gcd(212, 37)\)
\(\gcd(4389, 2919)\)
Using the Euclidean algorithm, we find \[\begin{align*} 57&=12\cdot 4+9\tag{1}\\ 12&=9\cdot 1+3\tag{2}\\ 9&=3\cdot3+0\tag{3}\end{align*}\] Thus, \(\gcd(12, 57) = 3\).
Using the Euclidean algorithm, we find \[\begin{align*} 212&=37\cdot 5+27\tag{1}\\ 37&=27\cdot 1+10\tag{2}\\ 27&=10\cdot 2+7\tag{3}\\ 10&=7\cdot 1+3\tag{4}\\ 7&=3\cdot 2+1\tag{5}\\ 3&=1\cdot 3+0\tag{6}\end{align*}\] Thus, \(\gcd(212, 37) = 1\).
Using the Euclidean algorithm, we find \[\begin{align*} 4389&=2919\cdot 1+1470\tag{1}\\ 2919&=1470\cdot 1+1449\tag{2}\\ 1470&=1449\cdot 1+21\tag{3}\\ 1449&=21\cdot 69+0\tag{4}\end{align*}\] Thus, \(\gcd(4389, 2919) = 21\).
For each of the following linear Diophantine equations, find a solution where \(x\) and \(y\) are integers, or explain why one does not exist.
\(4389x+2919y=21\)
\(4389x+2919y=231\)
\(212x - 37 y =1\)
\(12x + 57y = 124\)
\(12x + 57y = 423\)
Since \(\gcd(4389, 2919)= 21\),
this linear Diophantine equation has a solution. To find a solution, we
will work backwards through the steps in the Euclidean algorithm in our
solution to Problem \(1\). \[\begin{align*}
21&=\underline{1470}-1\cdot\underline{1449} & \text{from (3)}\\
&=\underline{1470}-1\cdot(\underline{2919}-1\cdot\underline{1470})&
\text{from (2)}\\
&=2\cdot\underline{1470}-1\cdot\underline{2919}\\
&=2\cdot(\underline{4389}-1\cdot\underline{2919})-1\cdot\underline{2919}
& \text{from (1)}\\
&=2\cdot\underline{4389}-3\cdot\underline{2919}\end{align*}\]
That is, \(4389(2) + 2919(-3) =21\).
Thus, one solution to the linear Diophantine equation \(4389x + 2919y = 21\) is \(x=2\), \(y=-3\).
Since \(\gcd(4389, 2919) = 21\) and \(231 = 21\times 11\), this linear Diophantine equation has a solution.
From part (a), we know that \[4389(2)+2919(-3)=21\] Multiplying both sides of the equation by \(11\): \[11(4389(2)+2919(-3))=11(21)\] or \[4389(22)+2919(-33)=231\] Thus, a solution to the linear Diophantine equation \(4389x+2919y=231\) is \(x=22\), \(y=-33\).
This is equivalent to solving the linear Diophantine equation \(212x + 37(-y) = 1\), or equivalently, \(212x+37z = 1\), where \(y=-z\).
From Problem 1, we know that \(\gcd(212, 37) = 1\), and so the linear Diophantine equation \(212x+37z = 1\) has a solution. To find a solution, we will work backwards through the steps in the Euclidean algorithm in our solution to Problem \(1\). \[\begin{align*} 1&=\underline{7}-2\cdot\underline{3}& \text{from (5)}\\ &=\underline{7}-2\cdot(\underline{10}-1\cdot\underline{7})& \text{from (4)}\\ &=3\cdot\underline{7}-2\cdot\underline{10}\\ &=3\cdot(\underline{27}-2\cdot\underline{10})-2\cdot\underline{10}& \text{from (3)}\\ &=3\cdot\underline{27}-8\cdot\underline{10}\\ &=3\cdot\underline{27}-8\cdot(\underline{37} - 1\cdot\underline{27})& \text{from (2)}\\ &=11\cdot\underline{27}-8\cdot\underline{37}\\ &=11\cdot(\underline{212} - 5\cdot\underline{37})-8\cdot\underline{37}& \text{from (1)}\\ &=11\cdot\underline{212}-63\cdot\underline{37}\\ &= 212(11) + 37(-63)\end{align*}\] Thus, one solution to the linear Diophantine equation \(212x+37z = 1\) is \(x=11\), \(z=-63\).
Therefore, a solution to \(212x - 37 y =1\) is \(x=11\), \(y=63\).
Since \(\gcd(12, 57)=3\), and \(3\) does not divide \(124\), there is no solution to this linear Diophantine equation where \(x\) and \(y\) are both integers.
Since \(\gcd(12, 57)=3\) and \(423 = 3 \times 141\), this linear Diophantine equation has a solution. To find a solution, we will first work backwards through the steps in the Euclidean algorithm in our solution to Problem \(1\). \[\begin{align*} 3&=\underline{12}-1\cdot\underline{9}& \text{from (2)}\\ &=\underline{12}-1\cdot(\underline{57}-4\cdot\underline{12})& \text{from (1)}\\ &=5\cdot\underline{12}-1\cdot\underline{57}\end{align*}\] Thus, \[12(5) + 57(-1) = 3\] Multiplying both sides of the equation by \(141\) gives, \[\begin{align*} 141(12(5) + 57(-1)) &= 141(3) \\ 12(141\cdot5) + 57(141\cdot(-1)) &= 423 \\ 12(705) + 57(-141) &= 423 \end{align*}\] Thus, one solution to the linear Diophantine equation \(12x + 57y = 423\) is \(x=705\), \(y=-141\).
Can \(1000\) be expressed as the sum of two integers, one of which is divisible by \(11\) and the other by \(17\)? If so, find examples of such integers. If not, explain why.
This problem is equivalent to asking if there is there a solution to the linear Diophantine equation \(11x + 17y = 1000\).
We know that there is a solution only if \(\gcd(11, 17)\) divides \(1000\).
Using the Euclidean algorithm, \[\begin{align*} 17&=11\cdot 1+6\tag{1}\\ 11&=6\cdot 1+5\tag{2}\\ 6&=5\cdot 1+1\tag{3}\\ 5&=1\cdot 5+0\tag{4}\end{align*}\] Thus, \(\gcd(11, 17) = 1\). Since \(1000\) is divisible by \(1\), there is a solution to this linear Diophantine equation.
We begin by first finding a solution to the linear Diophantine equation \(11x + 17y = 1\). Working backwards through our steps in the Euclidean algorithm, we have \[\begin{align*} 1&=\underline{6}-1\cdot\underline{5}& \text{from (3)}\\ &=\underline{6}-1\cdot(\underline{11}-1\cdot\underline{6})& \text{from (2)}\\ &=2\cdot\underline{6}-1\cdot\underline{11}\\ &=2\cdot(\underline{17} - 1\cdot\underline{11})-1\cdot\underline{11}& \text{from (1)}\\ &=2\cdot\underline{17}-3\cdot\underline{11}\end{align*}\] Thus, \(11(-3) + 17(2) = 1\).
Multiplying both sides of this equation by \(1000\) gives \[\begin{align*} 1000(11(-3) + 17(2)) &= 1000(1) \\ 11(-3\cdot1000) + 17(2\cdot1000) &= 1000 \\ 11(-3000) + 17(2000) &= 1000 \end{align*}\] Thus, one solution to the linear Diophantine equation \(11x + 17y = 1000\) is \(x=-3000\), \(y=2000\).
Therefore, \(1000\) can be expressed as the sum of \(-33000\) (which is divisible by \(11\)) and \(34000\) (which is divisible by \(17\)).
Can \(1000\) be expressed as the sum of two integers, one of which is divisible by \(9\) and the other by \(12\)? If so, find examples of such integers. If not, explain why.
This problem is equivalent to asking if there is a solution to the linear Diophantine equation \(9x + 12y = 1000\).
We know that there is a solution only if \(\gcd(9, 12)\) divides \(1000\).
By inspection, \(\gcd(9, 12) = 3\).
Since \(1000\) is not divisible by
\(3\), there is no integer solution to
the linear Diophantine equation \(9x + 12y =
1000\).
Therefore, \(1000\) cannot be expressed as the sum of two integers, one of which is divisible by \(9\) and the other by \(12\).
Use the Euclidean algorithm to find a solution to \(25x+10y=215\), the linear Diophantine equation from Example \(1\) in the Lesson. Does your answer make sense in the context of the problem? If not, how can we find a solution that does make sense?
When solving a linear Diophantine equation, our first step is always to find the gcd of the coefficients using the Euclidean algorithm: \[\begin{align*} 25&=10(2)+5\\ 10&=5(2)+0\end{align*}\] We end the Euclidean algorithm to find that \(\gcd(25,10)=5\).
Does \(5\) divide \(215\)? Yes! This means that the linear Diophantine equation \(25x+10y=215\) has a solution. To find it, we work backwards through the Euclidean algorithm.
Since our algorithm ended so quickly, it is easy to see that \(5=25-10(2)\).
By multiplying both sides of this equation by \(\frac{215}{5}=43\), we get \[25(43)+10(-86)=215\]
The answer does not make sense in the context of the problem. This answer suggests that we should use \(43\) quarters and \(-86\) dimes to total \(\$2.15\).
What we are really looking for is a solution to the linear Diophantine equation \[25x+10y=215\] where both \(x\) and \(y\) are non-negative integers.
One way to rectify this problem is the following: for every \(5\) dimes we are told to subtract, we just add \(2\) fewer quarters (since \(5\) dimes and \(2\) quarters both total \(50\) cents). So by taking away \(36=2(18)\) quarters, we can add \(90=5(18)\) dimes. This means that \(x=43-36=7\) and \(y=-86+90=4\) is another solution to the linear Diophantine equation \[25x+10y=215\] That is, Sara can buy the coffee with \(7\) quarters and \(4\) dimes. We will further discuss constraints like this in the second lesson on linear Diophantine equations.
Find an integer \(n\), which, when divided by \(78\) leaves a remainder of \(37\), and when divided by \(29\) leaves a remainder of \(17\).
If \(n\) has a remainder of \(37\) when divided by \(78\), then by the division algorithm we can write \[n = 78x + 37\tag{1}\] for some integer \(x\) Likewise, the same \(n\) may be written as \[n = 28y + 17\tag{2}\] for some integer \(y\) Since \(n\) is the same in both equations, it must be the case that \(78x+37=29y+17.\) By rearranging the terms, we arrive at the linear Diophantine equation \[78x-29y=-20.\]
If we can find a solution to this linear Diophantine equation, we can use equation \((1)\) or \((2)\) to obtain \(n\).
Our first step is to find \(\gcd(78,29)\). Using the Euclidean algorithm, \[\begin{align*} 78&=29(2)+20\tag{3}\\ 29&=20(1)+9\tag{4}\\ 20&=9(2)+2\tag{5}\\ 9&=2(4)+1\tag{6}\\ 2&=1(2)+0\tag{7}\end{align*}\]
Thus we know that \(\gcd(78,29)=\gcd(29,20)=\gcd(20,9)=\gcd(9,2)=\gcd(2,1)=\gcd(1,0)=1\).
We end the Euclidean algorithm to find that \(\gcd(78,29)=1\). Since \(1\) divides \(-20\), a solution to the linear Diophantine equation \(78x - 29y = -20\) exists. To find a solution, we have to work backwards through the Euclidean algorithm.
From \((6)\): \[1= 9-\underline{2}(4)\] Substituting for \(2\) using \((5)\): \[1= 9-[20-9(2)](4)\] Simplifying: \[1= \underline{9}(9)-20(4)\] Substituting for \(9\) using \((4)\): \[1= [29-20(1)](9)-20(4)\] Simplifying: \[1=29(9)-\underline{20}(13)\] Substituting for \(20\) using \((4)\): \[1=29(9)-[78-29(2)](13)\] Simplifying: \[1=78(-13)+29(35)\] This means that \(78(-13)+29(35)=1\).
Multiplying both sides of the equation \(78(-13)+29(35)=1\) by \(-20\), the equation becomes \[78(260)+29(-700)=-20\] Or equivalently, \[78(260)-29(700)=-20\]
Hence, a solution to the linear Diophantine equation \(78x - 29y = -20\) is \(x=260, y=700\).
We may now use either equation \((1)\) or equation \((2)\) to get \(n\). By substituting \(x=260\) into equation \((1)\), we get \(n=20\,317\).
Suppose \(a\), \(b\), and \(c\) are given integers. If \(ax^2 + by^2 = c\) has a solution where \(x\) and \(y\) are integers, is it true that \(\gcd(a,b)\) divides \(c\)? Why or why not?
Suppose \(a\), \(b\), and \(c\) are given integers. If \(\gcd(a,b)\) divides \(c\), is it true that \(ax^2 + by^2 = c\) always has a solution where \(x\) and \(y\) are integers? Why or why not?
Yes, this must be true. Suppose it is not true. That is, suppose \(c\) is not divisible by \(\gcd(a,b)\). Let’s divide both sides of the equation \(ax^2 + by^2 = c\) by \(\gcd(a,b)\). Since both \(a\) and \(b\) are divisible by \(\gcd(a,b)\), after dividing by \(\gcd(a,b)\), the left side can be written as \(nx^2+my^2\) for some integers \(n\) and \(m\). Thus, after dividing by \(\gcd(a,b)\), we have \[nx^2 + my^2 = \frac{c}{\gcd(a,b)}\] Here, \(n\), \(x\), \(m\), and \(y\) are integers, and so \(nx^2 + my^2\) is an integer. But \(\frac{c}{\gcd(a,b)}\) is not an integer, since \(c\) is not divisible by \(\gcd(a,b)\). So this last equality is impossible! Therefore, if \(c\) is not divisible by \(\gcd(a,b)\), there cannot be a solution to \(ax^2 + by^2 = c\) where \(x\) and \(y\) are integers. Thus, if there is a solution to \(ax^2 + by^2 = c\) where \(x\) and \(y\) are integers, it must be the case that \(\gcd(a,b)\) divides \(c\).
No, this is not necessarily true. Consider when \(a=1\), \(b=1\), and \(c=3\). We know that \(\gcd(a,b) = \gcd(1,1) = 1\). Also, \(c=3\) is divisible by \(1\). However, there are no integers that satisfy the equation \(x^2 + y^2 = 3\).
Use the division algorithm and the important fact to show that \(\gcd(k+1,k)=1\) for any integer \(k\geq 1\).
Use the division algorithm and the important fact to show that \[\gcd(7k+6,6k+5)=1\] for any integer \(k\geq 1\).
Recall from the important fact, that if \(a=bq+r\), then \(\gcd(a,b)=\gcd(b,r)\). How can we use this to solve our problem?
Well, we can write \[(k+1)=k(1)+1\] Here \(k+1\) is playing the role of \(a\), \(k\) is playing the role of \(b\), and \(1\) is playing the roles of \(q\) and \(r\). Thus, \[\gcd(k+1,k)=\gcd(k,1)=1\]
We’re going to try an approach similar to that in part (a). First, let’s use the division algorithm once to write \[(7k+6)=(6k+5)(1)+(k+1)\] Here, \(7k+6\) is playing the role of \(a\), \(6k+5\) is playing the role of \(b\), \(1\) is playing the role of \(q\), and \(k\) is playing the role of \(r\). We deduce from the important fact that \[\gcd(7k+6,6k+5)=\gcd(6k+5,k+1)\]
Again, we’ll apply the division algorithm to our new pair to get \[(6k+5)=(k+1)(5)+k\] Now the roles of \(a,b,q\) and \(r\) are played by \(6k+5\), \(k+1\), \(5\), and \(k\), respectively. The important fact tells us that \[\gcd(6k+5,k+1)=\gcd(k+1,k)\]
From part (a), we know that \(\gcd(k+1,k) = 1\).
Putting this all together, we get \[\gcd(7k+6,6k+5)=\gcd(6k+5,k+1)=\gcd(k+1,k)=1\]