Grade 9/10 Math Circles
Linear Diophantine Equations Part 1 - Problem Set

1. Using the Euclidean algorithm, we find $$\begin{array}{rl}57& =12\cdot 4+9\\ 12& =9\cdot 1+3\\ 9& =3\cdot 3+0\end{array}$$ Thus, $gcd(12,57)=3$.

2. Using the Euclidean algorithm, we find $$\begin{array}{rl}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{array}$$ Thus, $gcd(212,37)=1$.

3. Using the Euclidean algorithm, we find $$\begin{array}{rl}4389& =2919\cdot 1+1470\\ 2919& =1470\cdot 1+1449\\ 1470& =1449\cdot 1+21\\ 1449& =21\cdot 69+0\end{array}$$ Thus, $gcd(4389,2919)=21$.

1. 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{array}{rlr}21& =\underset{―}{1470}-1\cdot \underset{―}{1449}& \text{from (3)}\\ & =\underset{―}{1470}-1\cdot (\underset{―}{2919}-1\cdot \underset{―}{1470})& \text{from (2)}\\ & =2\cdot \underset{―}{1470}-1\cdot \underset{―}{2919}\\ & =2\cdot (\underset{―}{4389}-1\cdot \underset{―}{2919})-1\cdot \underset{―}{2919}& \text{from (1)}\\ & =2\cdot \underset{―}{4389}-3\cdot \underset{―}{2919}\end{array}$$ That is, $4389(2)+2919(-3)=21$. Thus, one solution to the linear Diophantine equation $4389x+2919y=21$ is $x=2$, $y=-3$.
   

2. 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$.

3. 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{array}{rlr}1& =\underset{―}{7}-2\cdot \underset{―}{3}& \text{from (5)}\\ & =\underset{―}{7}-2\cdot (\underset{―}{10}-1\cdot \underset{―}{7})& \text{from (4)}\\ & =3\cdot \underset{―}{7}-2\cdot \underset{―}{10}\\ & =3\cdot (\underset{―}{27}-2\cdot \underset{―}{10})-2\cdot \underset{―}{10}& \text{from (3)}\\ & =3\cdot \underset{―}{27}-8\cdot \underset{―}{10}\\ & =3\cdot \underset{―}{27}-8\cdot (\underset{―}{37}-1\cdot \underset{―}{27})& \text{from (2)}\\ & =11\cdot \underset{―}{27}-8\cdot \underset{―}{37}\\ & =11\cdot (\underset{―}{212}-5\cdot \underset{―}{37})-8\cdot \underset{―}{37}& \text{from (1)}\\ & =11\cdot \underset{―}{212}-63\cdot \underset{―}{37}\\ & =212(11)+37(-63)\end{array}$$ Thus, one solution to the linear Diophantine equation $212x+37z=1$ is $x=11$, $z=-63$.

   Therefore, a solution to $212x-37y=1$ is $x=11$, $y=63$.

4. 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.

5. 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{array}{rlr}3& =\underset{―}{12}-1\cdot \underset{―}{9}& \text{from (2)}\\ & =\underset{―}{12}-1\cdot (\underset{―}{57}-4\cdot \underset{―}{12})& \text{from (1)}\\ & =5\cdot \underset{―}{12}-1\cdot \underset{―}{57}\end{array}$$ Thus, $$12(5)+57(-1)=3$$ Multiplying both sides of the equation by $141$ gives, $$\begin{array}{rl}141(12(5)+57(-1))& =141(3)\\ 12(141\cdot 5)+57(141\cdot (-1))& =423\\ 12(705)+57(-141)& =423\end{array}$$ Thus, one solution to the linear Diophantine equation $12x+57y=423$ is $x=705$, $y=-141$.

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{array}{rl}17& =11\cdot 1+6\\ 11& =6\cdot 1+5\\ 6& =5\cdot 1+1\\ 5& =1\cdot 5+0\end{array}$$ 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{array}{rlr}1& =\underset{―}{6}-1\cdot \underset{―}{5}& \text{from (3)}\\ & =\underset{―}{6}-1\cdot (\underset{―}{11}-1\cdot \underset{―}{6})& \text{from (2)}\\ & =2\cdot \underset{―}{6}-1\cdot \underset{―}{11}\\ & =2\cdot (\underset{―}{17}-1\cdot \underset{―}{11})-1\cdot \underset{―}{11}& \text{from (1)}\\ & =2\cdot \underset{―}{17}-3\cdot \underset{―}{11}\end{array}$$ Thus, $11(-3)+17(2)=1$.

Multiplying both sides of this equation by $1000$ gives $$\begin{array}{rl}1000(11(-3)+17(2))& =1000(1)\\ 11(-3\cdot 1000)+17(2\cdot 1000)& =1000\\ 11(-3000)+17(2000)& =1000\end{array}$$ 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$).

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$.

When solving a linear Diophantine equation, our first step is always to find the gcd of the coefficients using the Euclidean algorithm: $$\begin{array}{rl}25& =10(2)+5\\ 10& =5(2)+0\end{array}$$ 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 $\mathrm{\$}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.

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{array}{rl}78& =29(2)+20\\ 29& =20(1)+9\\ 20& =9(2)+2\\ 9& =2(4)+1\\ 2& =1(2)+0\end{array}$$

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-\underset{―}{2}(4)$$ Substituting for $2$ using $(5)$: $$1=9-[20-9(2)](4)$$ Simplifying: $$1=\underset{―}{9}(9)-20(4)$$ Substituting for $9$ using $(4)$: $$1=[29-20(1)](9)-20(4)$$ Simplifying: $$1=29(9)-\underset{―}{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=20317$.

1. 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 $a{x}^2+b{y}^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 $n{x}^2+m{y}^2$ for some integers $n$ and $m$. Thus, after dividing by $gcd(a,b)$, we have $$n{x}^2+m{y}^2=\frac{c}{gcd(a,b)}$$ Here, $n$, $x$, $m$, and $y$ are integers, and so $n{x}^2+m{y}^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 $a{x}^2+b{y}^2=c$ where $x$ and $y$ are integers. Thus, if there is a solution to $a{x}^2+b{y}^2=c$ where $x$ and $y$ are integers, it must be the case that $gcd(a,b)$ divides $c$.

2. 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$.

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$$

2. 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$$