Grade 9/10 Math Circles
Linear Diophantine Equations Part 2 - 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. To find a solution, we will work backwards through the steps in the Euclidean algorithm in our solution to part (a). $$\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$$ Thus, one solution to the linear Diophantine equation $12x+57y=3$ is $x=5$, $y=-1$.

3. In part (b), we found that one solution to the linear Diophantine equation $12x+57y=3$ is $x=5$, $y=-1$.

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

4. In part (c), we found that one solution to the linear Diophantine equation $12x+57y=423$ is $x=705$, $y=-141$.

   To determine the complete solution, we calculate: $$x=705+n\left(\frac{b}{d}\right),y=-141-n\left(\frac{a}{d}\right)$$ Substituting $a=12$, $b=57$, and $d=3$: $$x=705+n\left(\frac{57}{3}\right),y=-141-n\left(\frac{12}{3}\right)$$ This simplifies to $x=705+19n$, $y=-141-4n$.

   Thus, the complete solution to the linear Diophantine equation $12x+57y=423$ is $x=705+19n$,  $y=-141-4n$, where $n$ is any integer.

5. In part (d), we found that the complete solution to the linear Diophantine equation $12x+57y=423$ is $x=705+19n$,  $y=-141-4n$, where $n$ is any integer.

   Now, we also require $x\ge 0$ and $y\ge 0$. Which values of $n$ will satisfy these conditions?

   $$\begin{array}{rl}x\ge 0& ⟹705+19n\ge 0\\ & ⟹19n\ge -705\\ & ⟹n\ge -37.105...\end{array}$$ So $n$ is an integer and $n\ge -37.105$, which tells us that $n\ge -37$.

   Similarly, $$\begin{array}{rl}y\ge 0& ⟹-141-4n\ge 0\\ & ⟹-4n\ge 141\\ & ⟹n\le -35.25\end{array}$$ So $n$ is an integer and $n\le -35.25$, which tells us that $n\le -36$.

   Thus, in order for $x\ge 0$ and $y\ge 0$, we must have $n\ge -37$ and also have $n\le -36$. Thus, there are $2$ possible values for $n$: $-36$, $-37$.

   Using $x=705+19n$ and $y=-141-4n$, we find there are two solutions to this problem. They are:

   • $x=21$, $y=3$ (when $n=-36$)

   • $x=2$, $y=7$ (when $n=-37$)

In Exercise $2$, we found that the complete solution to the linear Diophantine equation $4182x+3689y=102$ is $x=90+217n$, $y=-102-246n$, where $n$ is any integer.

Now, we also require $x\ge 0$ and $y\ge 0$. Which values of $n$ will satisfy these conditions?

$$\begin{array}{rl}x\ge 0& ⟹90+217n\ge 0\\ & ⟹217n\ge -90\\ & ⟹n\ge -0.4147...\end{array}$$ So $n$ is an integer and $n\ge -0.4147$, which tells us that $n\ge 0$.

Similarly, $$\begin{array}{rl}y\ge 0& ⟹-102-246n\ge 0\\ & ⟹-246n\ge 102\\ & ⟹n\le -0.4146...\end{array}$$ So $n$ is an integer and $n\le -0.4146$, which tells us that $n\le -1$.

Thus, in order for $x\ge 0$ and $y\ge 0$, we must have $n\ge 0$ and also have $n\le -1$. There are no values of $n$ that satisfy both of these inequalities simultaneously. Therefore, there is no solution to the linear Diophantine equation $4182x+3689y=102$ with $x\ge 0$ and $y\ge 0$.

In Problem Set #3 for Part 1 we were asked to find one way to express $1000$ as the sum of two integers, one which is divisible by $11$ and the other by $17$.

In the solution, we saw that this problem is equivalent to asking if there is a solution to the linear Diophantine equation $11x+17y=1000$, and we saw that one solution is $x=-3000$ and $y=2000$. (So the two numbers are $-33000$, which is divisible by $11$, and $34000$, which is divisible by $17$.)

We are now looking to find a solutions where both $x$ and $y$ are positive.

First, we can determine the complete solution by calculating: $$x=-3000+n\left(\frac{b}{d}\right),y=2000-n\left(\frac{a}{d}\right)$$ Substituting $a=11$, $b=17$, and $d=1$: $$x=-3000+17n,y=2000-11n$$

Thus, the complete solution to the linear Diophantine equation $11x+17y=1000$ is $x=-3000+17n,y=2000-11n$, where $n$ is any integer.

Now, we also require $x>0$ and $y>0$. Which values of $n$ will satisfy these conditions? $$\begin{array}{rl}x>0& ⟹-3000+17n>0\\ & ⟹17n>3000\\ & ⟹n>176.47...\end{array}$$ So $n$ is an integer and $n>176.47$, which tells us that $n\ge 177$.

Similarly, $$\begin{array}{rl}y>0& ⟹2000-11n>0\\ & ⟹-11n>-2000\\ & ⟹n<181.818...\end{array}$$ So $n$ is an integer and $n<181.818$, which tells us that $n\le 181$.

Thus, when both $n\ge 177$ and $n\le 181$, we will have $x\ge 0$ and $y\ge 0$.

Thus, there are $5$ possible values for $n$: $177$, $178$, $179$, $180$, $181$.

Using $x=-3000+17n$ and $y=2000-11n$, we find the five solutions to this problem where the two numbers are non-negative. They are:

• $n=177$: $x=9$, $y=53$, so the two numbers that sum to $1000$ are $99$ and $901$.

• $n=178$: $x=26$, $y=42$, so the two numbers that sum to $1000$ are $286$ and $714$.

• $n=179$: $x=43$, $y=31$, so the two numbers that sum to $1000$ are $473$ and $527$.

• $n=180$: $x=60$, $y=20$, so the two numbers that sum to $1000$ are $660$ and $340$.

• $n=181$: $x=77$, $y=9$, so the two numbers that sum to $1000$ are $847$ and $153$.

Let $a$ be the number of adult tickets and $s$ be the number of student tickets purchased.

Since an adult ticket costs $\mathrm{\$}34$ and a student ticket costs $\mathrm{\$}28$ and a total of $\mathrm{\$}844$ was spent on tickets, we are interested in solving the linear Diophantine equation

We first use the Euclidean Algorithm to calculate $gcd(34,28)$: $$\begin{array}{r}\text{setcounter}equation034=28\cdot 1+6\\ 28=6\cdot 4+4\\ 6=4\cdot 1+2\\ 4=2\cdot 2+0\end{array}$$ So $gcd(34,28)=2$. Since $844$ is divisible by $2$, there is a solution to this linear Diophantine equation.

We find a solution to $34a+28s=2$ by working backwards through our steps from the Euclidean Algorithm: $$\begin{array}{rlr}2& =6-1\cdot \underset{―}{4}& \text{from (3)}\\ & =6-1(28-4\cdot 6)& \text{from (2)}\\ & =5\cdot \underset{―}{6}-1\cdot 28\\ & =5(34-1\cdot 28)-1\cdot 28& \text{from (1)}\\ & =5(34)-6(28)\end{array}$$ Therefore, $34(5)+28(-6)=2$.

Multiplying both sides by $422$: $$\begin{array}{rl}422[34(5)+28(-6)]& =422(2)\\ 34(422(5))+28(422(-6))& =844\\ 34(2110)+28(-2532)& =844\end{array}$$

So a solution is $a=2110$ and $s=-2532$. Thus, the complete solution is:
$a=2110+n(\frac{28}{2})=2110+14n$ and $s=-2532-n(\frac{34}{2})=-2532-17n$

Since $a$ and $s$ represent the number of tickets sold, we need $a\ge 0$ and $s\ge 0$.

$a\ge 0$ means that $2110+14n\ge 0$, thus $14n\ge -2110$ and $n\ge -150.71...$ 

Since $n$ is an integer, we need $n\ge -150$.

$s\ge 0$ means that $-2532-17n\ge 0$, thus $-17n\ge 2532$ and $n\le -148.94...$
Since $n$ is an integer, we need $n\le -149$.

Thus, given the context of the problem, it must be the case that $-150\le n\le -149$.

When $n=-150$, we obtain $a=2110+14n=2110+14(-150)=10$ and $s=-2532-17n=-2532-17(-150)=18$.

When $n=-149$, we obtain $a=2110+14n=2110+14(-149)=24$ and $s=-2532-17n=-2532-17(-149)=1$.

Therefore, there are two possibilities for the tickets purchased. There could have been $10$ adult tickets and $18$ student tickets purchased, or $24$ adult tickets and $1$ student ticket purchased.

We need to first solve $157x=24y+10$ for integers $x$ and $y$.
In other words, we need to solve the linear Diophantine equation $157x-24y=10$.
We first use the Euclidean Algorithm, to calculate $gcd(157,24)$: $$\begin{array}{rl}157& =24\cdot 6+13\\ 24& =13\cdot 1+11\\ 13& =11\cdot 1+2\\ 11& =2\cdot 5+1\\ 2& =1\cdot 2+0\end{array}$$ Working backwards through these steps, we obtain: $$\begin{array}{rlr}1& =\underset{―}{11}-5\cdot \underset{―}{2}& \text{from (4)}\\ & =\underset{―}{11}-5\cdot (\underset{―}{13}-1\cdot \underset{―}{11})& \text{from (3)}\\ & =6\cdot \underset{―}{11}-5\cdot \underset{―}{13}\\ & =6\cdot (\underset{―}{24}-1\cdot \underset{―}{13})-5\cdot \underset{―}{13}& \text{from (2)}\\ & =6\cdot \underset{―}{24}-11\cdot \underset{―}{13}\\ & =6\cdot \underset{―}{24}-11\cdot (\underset{―}{157}-6\cdot \underset{―}{24})& \text{from (1)}\\ & =72\cdot \underset{―}{24}-11\cdot \underset{―}{157}\end{array}$$ Therefore, $157(-11)-24(-72)=1$.

Multiplying both sides of this equation by 10: $$\begin{array}{rl}10[157(-11)-24(-72)]& =10(1)\\ 157(10(-11))-24(10(-72))& =10\\ 157(-110)-24(-720)& =10\end{array}$$

Therefore, one solution to $157x-24y=10$ is $x=-110$,  $y=-720$.

Thus, the complete solution is
$x=-110+(\frac{-24}{1})n=-110-24n$ and $y=-720-(\frac{157}{1})n=-720-157n$

We are asked for the smallest positive value of $x$. In order to have $x\ge 0$, we would need $x=-110-24n\ge 0$. This implies that $24n\le -110$, or $n\le -4.583...$.

Since $n$ is an integer, this implies that we must have $n\le -5$.

So the smallest possible value for $x$ is when $n=-5$, and we have $x=-110-24(-5)=10$.

Indeed, we can check. When $x=10$, then $157x=1570$, which has remainder $10$ when divided by $24$.

Let $q$ represent the number of quarters, $d$ represent the number of dimes and $n$ represent the number of nickels.

From the information given in the problem, we have $$\begin{array}{rl}q+d+n& =1000\\ 25q+10d+5n& =20000\end{array}$$ Dividing equation $(2)$ by $5$, we obtain $$\begin{array}{rl}5q+2d+n& =4000\end{array}$$ Subtracting equation $(1)$ from equation $(3)$, we obtain: $4q+d=3000$.

Thus, we need to solve the linear Diophantine equation $4q+d=3000$.

By inspection, one solution to $4q+d=3000$ is $q=0$, $d=3000$.

Therefore, the complete solution is
$q=0+(\frac{1}{1})k=k$ and $d=3000-(\frac{4}{1})k=3000-4k$, where $k$ is any integer.

Since $q+d+n=1000$, we have $n=1000-q-d=1000-k-(3000-4k)=3k-2000$.

Since $q,d$ and $n$ represent coins, we also have the constraints $q\ge 0$, $d\ge 0$, and $n\ge 0$.

Since $q\ge 0$ and $q=k$, we have $k\ge 0$.

Since $d\ge 0$ and $d=3000-4k$, we have $3000-4k\ge 0$. Solving, we find that $4k\le 3000$, and thus $k\le 750$.

Since $n\ge 0$ and $n=3k-2000$, we have $3k-2000\ge 0$. Solving, we find that $3k\ge 2000$, and thus $k\ge 666.\overline{6}$. Since $k$ must be an integer, we need $k\ge 667$.

Thus, $667\le k\le 750$.

Therefore, there are $750-667+1=84$ ways to make exactly $\mathrm{\$}200$ using exactly $1000$ coins if each is a quarter, dime, or a nickel.

Solutions to the linear Diophantine equation $ax+by=c$ correspond to points on the line $y=-{\displaystyle \frac{a}{b}}x+{\displaystyle \frac{c}{b}}$.

This line has slope $-{\displaystyle \frac{a}{b}}$ and $y$-intercept ${\displaystyle \frac{c}{b}}$.

We can find the $x$-intercept of this line by setting $y=0$ and solving for $x$: $$0=-{\displaystyle \frac{a}{b}}x+{\displaystyle \frac{c}{b}}⟹{\displaystyle \frac{a}{b}}x=\frac{c}{b}⟹x=\frac{cb}{ab}=\frac{c}{a}$$

Therefore, this line has $x$-intercept ${\displaystyle \frac{c}{a}}$.

The graph of this line looks something like this:

Notice that the non-negative solutions to the linear Diophantine equation $ax+by=c$ are exactly the integer points that lie on the line segment from $(0,\frac{c}{b})$ to $(\frac{c}{a},0)$. How many of these points can there be?

Since $0\le x\le {\displaystyle \frac{c}{a}}$, there are at most ${\displaystyle \frac{c}{a}}$ such points.

Likewise, since $0\le y\le {\displaystyle \frac{c}{b}}$, there are at most ${\displaystyle \frac{c}{b}}$ such points.

Therefore, the number of integer solutions to the linear Diophantine equation $ax+by=c$ with $x\ge 0$ and $y\ge 0$ cannot exceed ${\displaystyle \frac{c}{a}}$ or ${\displaystyle \frac{c}{b}}$