じゃ，簡単ですね．
a_0,a_1とi = 0から順に順に
a_i = Q a_{i + 1} + a_{i + 2}
ここにa_{i + 1} > a_{i + 2}
となるようにa_iを決めていって，0になる直前のものが公約数ですね．

あとは割り算を，小学校でやったように取れるだけ取り除く，
と言う風に解釈するだけです．
例えば17を5で割るなら
17
-5
-5
-5 = 2でもう引けないから，17のとこに5を，
5のところに2を代入，とそれだけ．
本当は考えればもう少し簡単に出来ますが，これでもよいかと思います．