0
$\begingroup$

How do I solve $6y + 5z = 960$ for $0 < y < z$ using the Extended Algorithm?

2 Answers 2

3

First, you use the Euclidean algorithm to find all integer solutions.

This is very simple here. Since $\gcd(6,5)=1$, and $1$ divides $960$, there are certainly integer solutions. You can write $1 = 6-5$ (that's the Euclidean algorithm at work, though perhaps not very impressively). Thus, one integer solution is obtained by multiplying through by $960$: $960 = 6(960) - 5(960)$. That is, $y=960$, $z=-960$.

Now, since the $\gcd$ of $6$ and $5$ is $1$, every other integer solution is of the form $y=960-5k$, $z=6k -960$. The values of $k$ for which $y$ is positive are those in which $5k\lt 960$, or $k\lt \frac{960}{5} = 192$. The values of $k$ for which $z$ is greater than $y$ are those in which $960-5k \lt 6k-960$, or equivalently, those in which $1920\lt 11k$, or $k\gt\frac{1920}{11} \gt 174$. Thus, the values are those in which $174\lt k\lt 192$.

So the solutions are $y=960-5k$, $z=6k-960$, $175\leq k\leq 191$.

2

You can see that $(y, z) = (0, 192)$ is a a solution; since you want $y, z > 0$, do not add it to your list. Since $\gcd(5,6) = 1$, we obtain the next possible solution by docking 6 from $z$ and adding 5 to $y$ to get $(5, 186)$. We keep this one since $y, z > 0$. Keep doing this until $y \ge z$ or until $y\le 0$ or $z \le 0$. You then have a list of solution-tuples.