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

I'm having trouble solving the following diophantine equation:

$8x + 13y = 1571$

For all the other examples I've worked through I've been able to use the euclidean algorithm and the solution shows up somewhere. That doesn't work in this case, and the $\text{gcd}(8, 13) = 1$, so I know a solution exists. So how would you solve a problem like this?

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

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$

• So where is the particular solution and how does continued fractions work? Does this work only when the gcd(a,b) = 1? – Samantha Smith Apr 14 '13 at 15:24
• @SamanthaSmith, observe that if $d=gcd(x,y)$, the right hand side must be divisible by $d$ to admit any solution. So, we can always divide either sides by $d$ as long as $d>1$ – lab bhattacharjee Apr 14 '13 at 15:29
• @SamanthaSmith, also may have a look into proofwiki.org/wiki/B%C3%A9zout's_Lemma – lab bhattacharjee Apr 14 '13 at 15:33

Using Euclidean algorithm you will find $x',y'\in\mathbb Z$ such that $8x'+13y'=1$. Multiplying through by 1571 we get $8(x'\cdot1571)+13(y'\cdot1571)=1571$.
Now set $x=x'\cdot1571$ and $y=y'\cdot1571$. How about all solutions?

$\rm 8x\!+\!13y = k = 3\!+\!8j\:\Rightarrow\:mod\ 8\!:\ 13y\equiv 3\:\Rightarrow\:y \equiv \dfrac{3}{13} \equiv \dfrac{3}{{-}3}\equiv -1\:\Rightarrow\: \color{#c00}{y = -1\!+\!8n}$

$$\rm\Rightarrow\ \ \ x\, =\, \dfrac{k\!-\!13\,\color{#c00}y}8\,=\, \dfrac{ 8j\!+\!3 \!-\!13\,(\color{#c00}{-1\!+\!8n})}8\,=\, j\!+\!2\!-\!13n$$

Your special case is $\rm\ k = 1571 = 3 + 8\cdot 196,\:$ so $\rm\ j = 196,\$ so $\rm\ (x,y) = (198,-1) + n(-13,8)$

Hint: $~8x+(8+5)y=8\cdot196+3\iff8~(x+y-196)+5y=3=8-5.~$ Can you take it from here ? ;-)

8x + 13y = 1571 is equivalent to 8x = 1571(mod 13) which reduces 8x = 11(mod13).

Solving x = 3(mod 13) or x = 3 + 13k. Substituting this x back into the original equation you get y = 119 - 8k. The complete solution is x = 3 + 13k and y = 119 - 8k. Recently, on this site I discovered the Euclid - Wallis Algorithm. This algorithm computes the gcd(m,n), solves the Diophantine equation mx + ny = gcd(m,n) and yields the continued fraction of m/n. This algorithm accomplishes all of this by a series of multiplications and subtractions. Using this algorithm I got x = 7855 - 13k and y = -4713 + 8k which is equivalent to the answer above and equivalent to the Extended Euclidean Algorithm.