Question
How many positive solutions are there to 15x+21y=261?
What I got so far
gcd 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