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,
$$
\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}...