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.

Solution 1:

As you observed, we can reduce to the case where $a$ and $b$ are relatively prime. Given relatively prime positive integers $a$ and $b$, and a positive $c$, we want to find the number of solutions of $ax+by=c$ in positive integers $x$, $y$.

We will give an exact answer, and a much simpler to compute approximate answer which could be off by $1$. The argument that leads to these answers is given below. The answers themselves come after the argument.

There are integers $x_0,y_0$, such that $ax_0+by_0=c$. A solution $(x_0,y_0)$ can be found by using the Extended Euclidean Algorithm to solve the equation $au+bv=1$, and multiplying through by $c$. The details can be found in many places. We will instead concentrate on the consequences. Note that the $x_0$ and $y_0$ found through this process will not be both positive.

Once we have found one solution $(x_0,y_0)$, all integer solutions of the equation $ax+by=c$ have the shape $x=x_0+bt$, $y=y_0-at$, where $t$ ranges over the integers. To produce the positive solutions, we want to find all integers $t$ such that $x>0$ and $y>0$.

So we need $y_0-at >0$, $x_0+bt>0$, or equivalently $$-\frac{x_0}{b}<t <\frac{y_0}{a}.$$

Exact Answer: The number of positive solutions $(x,y)$ is the number of integers $t$ in the interval $-x_0/b<t <y_0/a$. This is easily determined once we know $x_0$ and $y_0$.

Approximate Answer: The interval $(-x_0/b,y_0/a)$ has width $y_0/a+x_0/b$. which simplifies to $(ax_0+by_0)/ab$, that is, $c/ab$.

If $\dfrac{c}{ab}$ is an integer, then the width of our open interval is an integer, and the number of integers in the interval is $\dfrac{c}{ab}-1$. If $\dfrac{c}{ab}$ is not an integer, then the number of integers in our open interval can be either $$\left\lfloor \dfrac{c}{ab}\right\rfloor \qquad \text{or}\qquad \left\lfloor \dfrac{c}{ab}\right\rfloor+ 1.$$

For a simple example that shows that $c/ab$ need not quite determine the number of positive solutions, note that $x+15y=23$ has one positive solution, while $3x+5y=23$ has two positive solutions.

If we give the answer $c/ab-1$ if $c/ab$ is an integer, and $\lfloor c/ab\rfloor$ otherwise, we are guaranteed that we are underestimating the true answer by at most $1$.

The advantage is that the approximate answer can be found very cheaply. In our exact answer, we used $x_0$ and $y_0$, so would need to compute these.

Solution 2:

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