# solving a linear diophantine equation in two variables

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?

• Have a look at the extended Euclidean algorithm. – Yves Daoust Jun 12 '18 at 21:28

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