Tuesday, 18 February 2014

elementary number theory - Solutions to Linear Diophantine equation 15x+21y=261



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,
12210125011372115630


The second to last column says that 315+(2)21=3, multiplying this by 87, yields 26115+(174)21=261. The last column says tha the general solution is (2617k)15+(174+5k)21=261. Using k=35,36,37, we get the 3 non-negative solutions:
1615+121=261915+621=261215+1121=261


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...