Grade 9/10 Linear Diophantine Equations 2 Problem Set

This problem will step you through determining all non-negative solutions to the linear Diophantine equation $12x+57y = 423$.

Use the Euclidean Algorithm to calculate $\gcd(12,57)$.
Using part (a), determine a solution to $12x + 57y =3$.
Using part (b), determine a solution to $12x+57y = 423$.
Using part (c), determine all solutions to $12x+57y = 423$.
Using your answer in part (d), determine all solutions to $12x+57y = 423$ with $x\geq 0$ and $y\geq 0$. That is, determine all non-negative solutions to the linear Diophantine equation $12x+57y = 423$.

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$.
To find a solution, we will work backwards through the steps in the Euclidean algorithm in our solution to part (a). \[\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\] Thus, one solution to the linear Diophantine equation $12x + 57y = 3$ is $x=5$, $y=-1$.
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{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$.
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), \quad y = -141 - n\left(\frac{a}{d}\right)\] Substituting $a=12$, $b=57$, and $d=3$: \[x = 705 + n\left(\frac{57}{3}\right), \quad 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.
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\geq 0$ and $y\geq 0$. Which values of $n$ will satisfy these conditions?

\[\begin{align*} x\geq 0 &\implies 705 +19n \geq 0\\ &\implies 19n\geq -705\\ &\implies n \geq -37.105...\end{align*}\] So $n$ is an integer and $n\geq -37.105$, which tells us that $n\geq -37$.

Similarly, \[\begin{align*} y\geq 0 &\implies -141 - 4n \geq 0\\ &\implies -4n\geq 141\\ &\implies n \leq -35.25\end{align*}\] So $n$ is an integer and $n\leq -35.25$, which tells us that $n\leq -36$.

Thus, in order for $x\geq 0$ and $y\geq 0$, we must have $n\geq -37$ and also have $n\leq -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$)

Explain why there is no solution to the linear Diophantine equation from Exercise $2$, \[4182x + 3689 y = 102\] with $x\geq0$ and $y\geq 0$.

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

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

\[\begin{align*} x\geq 0 &\implies 90 +217n \geq 0\\ &\implies 217n\geq -90\\ &\implies n \geq -0.4147...\end{align*}\] So $n$ is an integer and $n\geq -0.4147$, which tells us that $n\geq 0$.

Similarly, \[\begin{align*} y\geq 0 &\implies -102 - 246n \geq 0\\ &\implies -246n\geq 102\\ &\implies n \leq -0.4146...\end{align*}\] So $n$ is an integer and $n\leq -0.4146$, which tells us that $n\leq -1$.

Thus, in order for $x\geq 0$ and $y\geq 0$, we must have $n\geq 0$ and also have $n\leq -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 + 3689 y = 102$ with $x\geq0$ and $y\geq 0$.

Determine all possible ways that $1000$ can be expressed as the sum of two positive integers, one which is divisible by $11$ and the other by $17$.

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 $-33\,000$, which is divisible by $11$, and $34\,000$, 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), \quad y = 2000 - n\left(\frac{a}{d}\right)\] Substituting $a=11$, $b=17$, and $d=1$: \[x = -3000 + 17n, \quad 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{align*} x> 0 &\implies -3000 + 17n > 0\\ &\implies 17n> 3000\\ &\implies n > 176.47...\end{align*}\] So $n$ is an integer and $n> 176.47$, which tells us that $n\geq 177$.

Similarly, \[\begin{align*} y> 0 &\implies 2000 - 11n > 0\\ &\implies -11n> -2000\\ &\implies n < 181.818...\end{align*}\] So $n$ is an integer and $n< 181.818$, which tells us that $n\leq 181$.

Thus, when both $n\geq 177$ and $n\leq 181$, we will have $x\geq 0$ and $y\geq 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$.

At a museum, an adult ticket costs $\$34$ and a student ticket costs $\$28$. A group visiting the museum spends exactly $\$844$ on tickets. Determine all possible combinations for the number of adult and student tickets they could have purchased.

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

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

$34a + 28s = 844$

We first use the Euclidean Algorithm to calculate $\gcd(34, 28)$: \[\begin{align*} \setcounter{equation}{0} 34=28\cdot 1+6\\ 28=6\cdot 4+4\\ 6=4\cdot 1+2\\ 4=2\cdot2+0\end{align*}\] 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{align*} 2 &= 6 - 1\cdot \underline{4} & \text{from (3)}\\ &= 6 - 1(28 - 4\cdot 6) & \text{from (2)}\\ &= 5\cdot \underline{6} - 1\cdot28\\ &= 5(34 - 1\cdot28) - 1\cdot28 & \text{from (1)}\\ &= 5(34) - 6(28)\end{align*}\] Therefore, $34(5) + 28(-6) = 2$.

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

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\geq 0$ and $s\geq 0$.

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

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

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

Thus, given the context of the problem, it must be the case that $-150\leq n\leq -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.

Find the smallest positive integer $x$ so that $157x$ leaves remainder $10$ when divided by $24$.

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{align*} 157&=24\cdot6+13\\ 24&=13\cdot1+11\\ 13&=11\cdot1+2\\ 11&=2\cdot5+1\\ 2&=1\cdot2+0\end{align*}\] Working backwards through these steps, we obtain: \[\begin{align*} 1&=\underline{11}-5\cdot\underline{2} & \text{from (4)}\\ &=\underline{11}-5\cdot(\underline{13}-1\cdot\underline{11})& \text{from (3)}\\ &=6\cdot\underline{11}-5\cdot\underline{13}\\ &=6\cdot(\underline{24} - 1\cdot\underline{13})-5\cdot\underline{13} & \text{from (2)}\\ &=6\cdot\underline{24}-11\cdot\underline{13}\\ &=6\cdot\underline{24}-11\cdot(\underline{157} - 6\cdot\underline{24}) &\text{from (1)}\\ &=72\cdot\underline{24}-11\cdot\underline{157}\end{align*}\] Therefore, $157(-11) -24(-72) = 1$.

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

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\geq 0$, we would need $x = -110 -24n \geq 0$. This implies that $24n \leq -110$, or $n\leq -4.583...$.

Since $n$ is an integer, this implies that we must have $n\leq -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$.

Determine the number of ways you can make exactly $\$200$ using exactly $1000$ coins if each coin is a quarter, a dime, or a nickel.

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{align*} q +d+n &= 1000\\ 25q + 10d + 5n &= 20\,000\end{align*}\] Dividing equation $(2)$ by $5$, we obtain \[\begin{align*} 5q + 2d + n &= 4000 \end{align*}\] 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\geq 0$, $d\geq 0$, and $n\geq 0$.

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

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

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

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

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

Let $a$, $b$, and $c$ be positive integers and consider the linear Diophantine equation $ax+by=c$. Show that the number of non-negative integer solutions to this equation cannot exceed $\dfrac{c}{a}$ or $\dfrac{c}{b}$.

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

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

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

Therefore, this line has $x$-intercept $\dfrac{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 $\left(0,\frac{c}{b}\right)$ to $\left(\frac{c}{a},0\right)$. How many of these points can there be?

Since $0\leq x \leq \dfrac{c}{a}$, there are at most $\dfrac{c}{a}$ such points.

Likewise, since $0\leq y \leq \dfrac{c}{b}$, there are at most $\dfrac{c}{b}$ such points.

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