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

-

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}

-
Thanks for this. I notice in this example and in other examples that the number of solutions correspond to the gcd. Is this true in general or just a coincidence? –  Arvin Nov 10 '11 at 12:31
It is just a coincidence. Note that $5x+7y=87$ also has $3$ solutions, yet the gcd is $1$. –  robjohn Nov 10 '11 at 12:58

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.

-

5, 7, and 87 are small enough numbers that you could just try all the possibilities. Can you see, for example, that $y$ can't be any bigger than 12?

-
I do see that, but I'd like to develop a more generalised method to doing these types of questions - in case I get asked bigger numbered questions in the future –  Arvin Nov 10 '11 at 11:48
The general method involves using Euclid's algorithm, and is presented in every introductory number theory textbook. I'm sure it's also all over the web - search for "linear diophantine equations". –  Gerry Myerson Nov 10 '11 at 11:55

Hint $\$ It's easy. $\rm\:x\ge 1\:\Rightarrow\: y = (87-5x)/7 \le \lfloor 82/7\rfloor = 11.\:$ Each of the intervals $[1,5], [6,10]$ contains precisely one solution for $\rm\:y,\:$ so it remains to check if $\rm\:y=11\:$ yields a solution.

Note that the (extended) Euclidean algorithm is not required, and this method works generally.

-

you find all solutions from $ax+by=c$ with

$$x=x_0-\frac{b}{(a,b)}*t , y=y_0+\frac{a}{(a,b)}*t$$

$x_0$ and $y_0$ you find with the Euclidean algorithm backwards:

$15x+21y=261$ with $261=3*87$

21=1*16+6

15=2*6+3

6=2*3+0

$3=15-2*6=15-2*(21-1*15)=15-2*21+2*15=3*15-2*21$

multiplied with 87 we get

$261=261*15-174*21$

So $x_0=261$ and $y_0=174$

-
Thanks, but what is $x_0$, $y_0$, $a$ and $b$ in this particular example? –  Arvin Nov 10 '11 at 11:49
$x_0$ and $y_0$ is one solution of your example, $a$ is the number in front of $x$ and $b$ is the number in front of $y$ –  ulead86 Nov 10 '11 at 11:50
What Daniel means is that if $ax_0+by_0=c$, that is, if $x_0,y_0$ is one solution of $ax+by=c$, then his formula gives you all the solutions, as you let $t$ run through the integers. But you only want the positive solutions, so you would also have to impose some restriction on $t$. Also, Daniel doesn't tell you how to find that first solution $x_0,y_0$. –  Gerry Myerson Nov 10 '11 at 11:55

$15x+21y=261$. $\Leftrightarrow x= \dfrac{261-21y}{15}=17-y+ \dfrac{6(1-y)}{15}$

Because $x,y$ are integer numbers and $\gcd(y,1-y)=1$. Therefore $15|1-y$. Let $1-y=15k$ with $k \in \mathbb{Z}$ implies $y=1-15k$. Thus $x=15+21k$.

Now, to find $x,y$ positive number, we will try the value of $k$.

-

5x + 7y = 87 can be rewritten as 5x = 87(mod 7). Solving x = 2(mod 7) which means that x = 2 + 7t. Substituting this x back into the equation you get y = 11 - 5t.

The complete solution is x = 2 + 7t and y = 11 - 5t. So there are an infinite number of solutions.

-