<s>[INST] How can I do the Euclidian's algorithm and the Extended Euclidean algorithm at the same time? This is what my lecture notes have but I cannot find anything like it online and there is no explanation in the notes. The example given is for 903 and 444. 

Thank you. 
 [/INST] I like to write these as (simple) continued fractions. 
$$  \gcd( 903, 444 ) = ???    $$  
$$ \frac{ 903 }{ 444 } = 2 +  \frac{ 15 }{ 444 } $$ 
 $$ \frac{ 444 }{ 15 } = 29 +  \frac{ 9 }{ 15 } $$ 
 $$ \frac{ 15 }{ 9 } = 1 +  \frac{ 6 }{ 9 } $$ 
 $$ \frac{ 9 }{ 6 } = 1 +  \frac{ 3 }{ 6 } $$ 
 $$ \frac{ 6 }{ 3 } = 2 +  \frac{ 0 }{ 3 } $$ 
 Simple continued fraction tableau:
 $$ 
 \begin{array}{cccccccccccc}
 & & 2 & & 29 & & 1 & & 1 & & 2 & \\ 
  \frac{ 0 }{ 1 }   &   \frac{ 1 }{ 0 }   & &   \frac{ 2 }{ 1 }   & &   \frac{ 59 }{ 29 }   & &   \frac{ 61 }{ 30 }   & &   \frac{ 120 }{ 59 }   & &   \frac{ 301 }{ 148 }  
 \end{array}
 $$ 
 $$  $$ 
 $$ 301 \cdot 59 - 148 \cdot 120 = -1 $$ 
$$  \gcd( 903, 444 ) = 3  $$
 $$ 903 \cdot 59 - 444 \cdot 120 = -3 $$ 
</s>