Exercise Solutions

Problem Set Solutions

1. Calculate the following gcds using the Euclidean algorithm.

   1. $gcd(12,57)$

   2. $gcd(212,37)$

   3. $gcd(4389,2919)$

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

   2. Using the Euclidean algorithm, we find $$\begin{array}{}\text{(1)}& 212& =37\cdot 5+27\text{(2)}& 37& =27\cdot 1+10\text{(3)}& 27& =10\cdot 2+7\text{(4)}& 10& =7\cdot 1+3\text{(5)}& 7& =3\cdot 2+1\text{(6)}& 3& =1\cdot 3+0\end{array}$$ Thus, $gcd(212,37)=1$.

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

2. For each of the following linear Diophantine equations, find a solution where $x$ and $y$ are integers, or explain why one does not exist.

   1. $4389x+2919y=21$

   2. $4389x+2919y=231$

   3. $212x-37y=1$

   4. $12x+57y=124$

   5. $12x+57y=423$

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

3. 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{array}{}\text{(1)}& 17& =11\cdot 1+6\text{(2)}& 11& =6\cdot 1+5\text{(3)}& 6& =5\cdot 1+1\text{(4)}& 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$).

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

5. 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{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.

6. 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 $$\begin{array}{}\text{(1)}& n=78x+37\end{array}$$ for some integer $x$ Likewise, the same $n$ may be written as $$\begin{array}{}\text{(2)}& n=28y+17\end{array}$$ 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{array}{}\text{(3)}& 78& =29(2)+20\text{(4)}& 29& =20(1)+9\text{(5)}& 20& =9(2)+2\text{(6)}& 9& =2(4)+1\text{(7)}& 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$.

7. 1. Suppose $a$, $b$, and $c$ are given integers. If $a{x}^2+b{y}^2=c$ has a solution where $x$ and $y$ are integers, is it true that $gcd(a,b)$ divides $c$? Why or why not?

   2. Suppose $a$, $b$, and $c$ are given integers. If $gcd(a,b)$ divides $c$, is it true that $a{x}^2+b{y}^2=c$ always has a solution where $x$ and $y$ are integers? Why or why not?

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

8. 1. Use the division algorithm and the important fact to show that $gcd(k+1,k)=1$ for any integer $k\ge 1$.

   2. Use the division algorithm and the important fact to show that $$gcd(7k+6,6k+5)=1$$ for any integer $k\ge 1$.

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