ユークリッドの互除法

作成者:
Bunryu Kamimura
ユークリッドの互除法とは、aとbの最大公約数を図形で求める方法。 )a b で素因数分解するよりもわかり易く、応用も広い。 このやり方でやれば必ず最大公約数を求めることができる世界最古のアルゴリズム。 数論だけど図形を用いているので幾何学といっても良い。 意味は下の図で確認できる。

右上の式を順番に確かめながらチェックしていってください。

確かめ

42と26の最大公約数を求めることは、この長方形を敷き詰めることのできる最も大きな正方形を求めることと同じである。  2で余りがなくなったのだから、2×4は2×2の正方形で敷き詰められる。  2×4が敷き詰められるのだから、4×4は当然2×2の正方形で敷き詰められる。・・・⑤  つまり4×6が敷き詰められるということ。  4×6が敷き詰められるのだから、6×6も2の正方形で敷き詰められる。・・・④  つまり6×10も敷き詰められる。  以下同様。  よって、42×26の長方形は2×2の正方形で敷き詰めることができる。  この2×2はこの長方形を敷き詰められる最も大きな正方形である。