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,
122101−2501−13−72115630
The second to last column says that 3⋅15+(−2)⋅21=3, multiplying this by 87, yields 261⋅15+(−174)⋅21=261. The last column says tha the general solution is (261−7k)⋅15+(−174+5k)⋅21=261. Using k=35,36,37, we get the 3 non-negative solutions:
16⋅15+1⋅21=2619⋅15+6⋅21=2612⋅15+11⋅21=261
No comments:
Post a Comment