互除法で最大公約数を求める

ユークリッドの互除法を用いて、198と72の最大公約数を求めよ。

18

$198=72\times2+54$、$72=54\times1+18$、$54=18\times3+0$。よって198と72の最大公約数は18である。