<s>[INST] 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: 

 [/INST] $$ \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 $$
..
</s>