Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

7 Answers 7

up vote 7 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

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?

share|improve this answer
    
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.

share|improve this answer

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$

share|improve this answer
    
Thanks, but what is $x_0$, $y_0$, $a$ and $b$ in this particular example? –  Arvin Nov 10 '11 at 11:49
1  
$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$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.