5
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ So where is the particular solution and how does continued fractions work? Does this work only when the gcd(a,b) = 1? $\endgroup$ – Samantha Smith Apr 14 '13 at 15:24
  • $\begingroup$ @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$ $\endgroup$ – lab bhattacharjee Apr 14 '13 at 15:29
  • $\begingroup$ @SamanthaSmith, also may have a look into proofwiki.org/wiki/B%C3%A9zout's_Lemma $\endgroup$ – lab bhattacharjee Apr 14 '13 at 15:33
0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

$\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)$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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