Question
How many positive solutions are there to $15x+21y=261$?
What I got so far
$\gcd(15,21) = 3$ and $3|261$
So we can divide through by the gcd and get:
$5x+7y=87$
And I'm not really sure where to go from this point. In particular, I need to know how to tell how many solutions there are.
Answer
Apply the Euclid-Wallis Algorithm,
$$
\begin{array}{r}
&&1&2&2\\
\hline\\
1&0&1&-2&5\\
0&1&-1&3&-7\\
21&15&6&3&0
\end{array}
$$
The second to last column says that $3\cdot15+(-2)\cdot21=3$, multiplying this by $87$, yields $261\cdot15+(-174)\cdot21=261$. The last column says tha the general solution is $(261-7k)\cdot15+(-174+5k)\cdot21=261$. Using $k=35,36,37$, we get the $3$ non-negative solutions:
$$
\begin{align}
16\cdot15+1\cdot21&=261\\
9\cdot15+6\cdot21&=261\\
2\cdot15+11\cdot21&=261\\
\end{align}
$$
No comments:
Post a Comment