solving a linear diophantine equation in two variables

Question

I'm a bit confused in applying the Euclidean algorithm to solve the following equation:

$$11x + 34 = 13y + 35$$

$$x,y\in\Bbb Z; \qquad0 < x,y$$

How can I go about solving it, if there are solutions?

Answer 1

Apply Euclids algorithm to $11$ and $13$ \begin{eqnarray*} 13-11=2 \\ 11-5 \times 2 =1. \end{eqnarray*} So \begin{eqnarray*} 1=11-5 \times 2 =11 -5(13-11)=\color{blue}{6}\times 11 \color{red}{-5}\times 13 \end{eqnarray*} and hence you have values for $\color{blue}{x}$ and $\color{red}{y}$.

The general solution is $\color{blue}{x=6+13k}$ and $\color{red}{y=-5-11k}$.

Answer 2

$11x - 13 y = 1$

$$ \gcd( 13, 11 ) = ??? $$

$$ \frac{ 13 }{ 11 } = 1 + \frac{ 2 }{ 11 } $$ $$ \frac{ 11 }{ 2 } = 5 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccc} & & 1 & & 5 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 6 }{ 5 } & & \frac{ 13 }{ 11 } \end{array} $$ $$ $$ $$ 13 \cdot 5 - 11 \cdot 6 = -1 $$

But you want $11 \cdot 6 - 13 \cdot 5 = 1$ which is true, $66-65$