ユークリッドの互除法
ユークリッドの互除法とは、ａとｂの最大公約数を図形で求める方法。
)a b で素因数分解するよりもわかり易く、応用も広い。
このやり方でやれば必ず最大公約数を求めることができる世界最古のアルゴリズム。
数論だけど図形を用いているので幾何学といっても良い。
意味は下の図で確認できる。
右上の式を順番に確かめながらチェックしていってください。
確かめ
４２と２６の最大公約数を求めることは、この長方形を敷き詰めることのできる最も大きな正方形を求めることと同じである。
２で余りがなくなったのだから、２×４は２×２の正方形で敷き詰められる。
２×４が敷き詰められるのだから、４×４は当然２×２の正方形で敷き詰められる。・・・⑤
つまり４×６が敷き詰められるということ。
４×６が敷き詰められるのだから、６×６も２の正方形で敷き詰められる。・・・④
つまり６×１０も敷き詰められる。
以下同様。
よって、４２×２６の長方形は２×２の正方形で敷き詰めることができる。
この２×２はこの長方形を敷き詰められる最も大きな正方形である。