An equation in two variables?

Question

Given 13x + 35y = 2000. How do I find positive integer solutions for this equation (without hit and trial).

My work :- I know I can use Bezout's Theorem to find integer solutions to this equation if I have first solution (x., y.). But I just want positive solutions. To find the first solution I tried using Euclid's algorithm but could not progress further. Please help. Or if you have a smaller way of doing this type of questions feel free to post them as answers. (for all integer solutions or only (+)ve integer solutions).

Answer 1

$13x+35y=400(70-65)$

$\iff13(x-2000)=35(800-y)$

$\implies \dfrac{13(x-2000)}{35}=800-y $ which is an integer

$\implies35$ divides $13(x-2000)$ hence $x-2000$

$x\equiv2000\pmod{35},x=35t+2000,t>-\dfrac{2000}{35}>-57,$

$13(35t)=35(800-y)\iff y=800-13t>0\iff t<?$

Answer 2

It's immediately obvious that $x$ has to be a multiple of $5$, if it has any hope of satisfying this. Hence write $x=5z$ and so we get:

$$35y+65z=2000$$

Now you can apply what Alfred suggested because $35+65=100$ which divides $2000$.

Answer 3

The following can only reduce the number of trials and may not exhaust all the solutions.

2000 = (16)(5)(5)(5)

Since a partial factor 5 appears from the ‘35’ and ‘2000’, that means a ’5’ is needed from 13x. Therefore, we should let x = 5h. Then, after cancelling the ‘5’, we have

13h + 7y = (16)(5)(5)

The RHS indicates there should be at least one more 5 from the LHS. Another thing we can try is let x = 25H instead and at the same time we let y = 5K. Then,

13H + 7K = 80 which is much easier to guess a possible solution.

The guessing process can be continued if we let H = 4H', ....

Answer 4

$\!\bmod 13\!:\ 35y\equiv 2000\!\iff\! -4y\equiv -2$ $\!\iff\! y\equiv \dfrac{1}2\equiv \dfrac{14}2\equiv 7$ $\!\iff x\equiv \dfrac{2000\!-\!35y}{13}\equiv 135$

Thus $\,(x,y) = (135,7)+n(-35,13)\,$ has $\,x,y>0\iff 0\le n \le 3$

Answer 5

We start by finding a solution to $35x+13y=1$

\begin{array}{r|r|rr|rl} & 35 & 1 & 0 & \color{red}{35} & \color{red}{= 1(35) + 0(13)}\\ -3 & 13 & 0 & 1 & \color{red}{13} & \color{red}{ = 0(35) + 1(13)}\\ 3 & -4 & 1 & -3 & \color{red}{-4} & \color{red}{ = 1(35) - 3(13)}\\ & 1 & 3 & -8 & \color{red}{ 1} & \color{red}{ = 3(35) - 8(13)}\\ \end{array}

We conclude that $$35(3)+13(-8)=1.$$

Hence a solution to $35x+13y=2000$ is

$$35(6000)+13(-16000)=2000.$$

We can therefore characterize all integer solutions to $35x + 13y = 2000$ by $$(x,y) = (6000 - 13t, 35t - 16000).$$

To find the smallest positive integer value of $x$, we solve

\begin{align} 6000 - 13t &> 0 \\ -13t &> -6000 \\ t & < 461\frac{7}{13} \\ t &\le 461 \end{align}

So, the smallest positive integer value of $x$ is $x = 6000-13(461) = 7$

The corresponding value of $y$ is $y = 35(461) - 2400 = 13735$

We can now recharacterize all integer solutions to $35x + 13y = 2000$ by $$(x,y) = (7 + 13t, 13735 - 35t).$$

Where $t=0$ gives $(x,y)=(7, 13735)$, the positive solution with the smallest possible value of $x$.

To find the smallest possible value of $y$, we solve

\begin{align} 13735 - 35t &> 0 \\ -35t &> -13735 \\ t &< 392\frac 37 \\ t &\le 392 \end{align}

So the smallest possible value of $y$ occurs when $t=392$, that is $y = 13735 - 35(392) = 15$

So the set of all positive solutions can be expressed as

$$\{(7 + 13t, 13735 - 35t) : t = 0,1,2, \dots, 392 \}$$