722と171の最大公約数を、ユークリッドの互除法を使って求めよう。

「AとB」の最大公約数は、「Bとr」の最大公約数と等しくなる のが互除法だよ。実際の互除法の手順は次のようにするんだ。

722を171で割ると、
722 ＝ 171 ×4+ 38 　となるね。
ユークリッドの互除法より、 722と171の最大公約数は、171と38の最大公約数と等しくなる ね。だいぶ数が小さくなったよ！

今度は、171を38で割ってみよう。
171 ＝ 38 ×4+ 19
171と38の最大公約数は、38と19の最大公約数と等しくなる んだ。

ここまで来ると、最大公約数はひと目で分かるね。
38＝19×2
つまり、 38と19の最大公約数は19 だ。
これをさかのぼって考えよう。 722と171の最大公約数は、38と19の最大公約数に等しいから19 だということが言えるんだよ。