Grade 9/10 Linear Diophantine Equations 1 Problem Set

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\\ 12&=9\cdot 1+3\\ 9&=3\cdot3+0\end{align*}\] Thus, $\gcd(12, 57) = 3$.
Using the Euclidean algorithm, we find \[\begin{align*} 212&=37\cdot 5+27\\ 37&=27\cdot 1+10\\ 27&=10\cdot 2+7\\ 10&=7\cdot 1+3\\ 7&=3\cdot 2+1\\ 3&=1\cdot 3+0\end{align*}\] Thus, $\gcd(212, 37) = 1$.
Using the Euclidean algorithm, we find \[\begin{align*} 4389&=2919\cdot 1+1470\\ 2919&=1470\cdot 1+1449\\ 1470&=1449\cdot 1+21\\ 1449&=21\cdot 69+0\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\\ 11&=6\cdot 1+5\\ 6&=5\cdot 1+1\\ 5&=1\cdot 5+0\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$.

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\\ 29&=20(1)+9\\ 20&=9(2)+2\\ 9&=2(4)+1\\ 2&=1(2)+0\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\]