互除法による最大公約数の求め方

　小学校か中学校か忘れたけど、学校で習った2つの数の最大公約数の求め方というのは、なにか公約数を見つけてそれで2つの数を割る、という作業を公約数が（1以外に）なくなるまで続けて、出てきた公約数を全部掛け合わせるというものだったよ。
　たとえば と の最大公約数を求めるには、どっちも で割れるから割ってやったら と になって、また で割れるから割ってやったら と になって、もう公約数がないからここでストップして出てきた公約数を掛け合わせて
　　
ということで が最大公約数だよ。
　でも公約数がなかなか見つからないときはこの方法は使えないよ。たとえば と の最大公約数は なんだけど、そもそもこれは素数で、つまりこの2つの数の公約数は と しかないわけで、どちらも で割り切れるということを発見するまでに、それから 以外の数では割り切れないということを確認するまでに、大変な時間と労力がかかるよ。
　こういうときはユークリッドの互除法というのを使うよ。これは、大きい方の数を小さい方で割って余りを出し、今度はその余りで先の計算の「割る数」を割るということを、割り切れるまで続けるやり方だよ。割り切れたときの「割る数」が最大公約数だよ。
　上の例でやってみるよ。
　　
　　
　　
　　
　　
　　
ということでめでたく最大公約数 が得られたよ。割り算の「商」は関係ないから無視していいよ。