# Euclidean GCD calculation and mod

Calculate $$6/87 \pmod{137}$$

I do not understand the Euclidean GCD algorithm. If someone can please explain the overall logic of this it would be much appreciated.I have posted what the solution is supposed to be below:

$$\dfrac{0}{137} \overset{\large\frown}\equiv\ \bbox[5px,border:1px solid red]{\dfrac{6}{87}}\overset{\large\frown}\equiv\ \dfrac{-6}{50}\overset{\large\frown}\equiv\dfrac{18}{-13}\overset{\large\frown}\equiv \dfrac{66}{-2}\equiv \dfrac{-33}1\equiv \bbox[5px,border:1px solid red]{ \dfrac{104}1}\pmod{137}$$
$$\frac{ 137 }{ 87 } = 1 + \frac{ 50 }{ 87 }$$ $$\frac{ 87 }{ 50 } = 1 + \frac{ 37 }{ 50 }$$ $$\frac{ 50 }{ 37 } = 1 + \frac{ 13 }{ 37 }$$ $$\frac{ 37 }{ 13 } = 2 + \frac{ 11 }{ 13 }$$ $$\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}{cccccccccccccccc} & & 1 & & 1 & & 1 & & 2 & & 1 & & 5 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 2 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 8 }{ 5 } & & \frac{ 11 }{ 7 } & & \frac{ 63 }{ 40 } & & \frac{ 137 }{ 87 } \end{array}$$  $$137 \cdot 40 - 87 \cdot 63 = -1$$