以下の手続きはユークリッドの互除法と同じものである。

15/11=1+4/11

11/4~2+3/4

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

35/21~1+14/21

21/14=1+7/14

14/7=2→(35,21)=7 (GCD)

ユークリッドの互除法の背後にある考え方は(a,b)=(a-kb,b)、すなわち、(a-kb＜b)によって、大きな数を扱いやすい大きさまで変えるのである。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝