How to solve the diophantine equation $8x + 13y = 1571$

Solution 1:

Start by solving the equation $8s+13t=1$. You can do this by inspection, for $s=-8$, $t=5$ obviously works. Or else you can use the machinery of the Euclidean Algorithm.

So $x_0=(-8)(1571)$, $y_0=(5)(1571)$ is a solution of the equation we were given.

All solutions of that equation are given by $x=x_0+13t$, $y=y_0-8t$, where $t$ ranges over the integers.

Remark: We need not have started from a solution of $8s+13t=1$. The only reason we did it that way was to connect the solution with material that you have already covered.

If we find any particular solution $(x_1,y_1)$ of our equation, then all solutions are given by $x=x_1+13t$, $y=y_1-8t$.

If you have done Linear Algebra, or Differential Equations, you have seen this kind of thing before. We got the general solution of our equation by taking a particular solution, and adding the general solution of the homogeneous equation $8x+13y=0$.

Solution 2:

Expanding as continued fraction we get $$\frac{13}8=1+\frac58=1+\frac1{\frac85}=1+\frac1{1+\frac35}$$ $$=1+\frac1{1+\frac1{\frac53}}=1+\frac1{1+\frac1{1+\frac23}}$$ $$=1+\frac1{1+\frac1{1+\frac1{\frac32}}}=1+\frac1{1+\frac1{1+\frac1{1+\frac12}}}$$

So, the last convergent is $$1+\frac1{1+\frac1{1+\frac1{1}}}=\frac53$$

Using the convergent property of continued fraction, $$ 8\cdot 5-13\cdot3=1$$

So, $$8x+13y=1571(8\cdot 5-13\cdot3)$$

$$8(x-5\cdot1571)=-13(3\cdot1571+y)$$

$$\frac{13(3\cdot1571+y)}8=5\cdot1571-x$$ which is an integer

So, $$8\mid 13(3\cdot1571+y)\implies 8\mid (3\cdot1571+y)\text{ as }(8,13)=1$$

$3\cdot1571+y\equiv0\pmod 8\iff 3\cdot3+y\equiv0\pmod 8$ as $1571\equiv3\pmod8$

$\implies y\equiv-9\pmod8\equiv7\implies y=8a+7$ for some integer $a$