Solutions to Linear Diophantine equation $15x+21y=261$

Question

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 1

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

Answer 2

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?

Answer 3

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$

Answer 4

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.

Answer 5

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.

Answer 6

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