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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

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