タイランド湾を見て暮らす・パタヤコージーライフ

Pattayaでのリタイヤライフです。旅行/日常生活/ゴルフ/鳥見/タイ語学習

ユークリッドの互除法

 いよいよというか、遅ればせながら、上記左の「ガロア理論の頂を踏む」(石井俊全著)に着手。本購入以来、500ページの大著なので、目次以降ページをめくるのも躊躇していました。著者の石井さんは東工大数学科修士卒。大人向けの数学セミナー等で著名な人。


 第1章第1課は「ユークリッドの互除法」でした。2300年前にユークリッドが著した「原論」所載の「最大公約数」を求めるアルゴリズムです。


 最大公約数を求めることは、高校数学の履修範囲ですが、通常、素因数分解をして求めます。ユークリッドの互除法は、参考書レベルには記載されている求め方で、計算そのものは簡単です。


 例えば、851と185の最大公約数を求める際の計算は、
 851÷185=4 余り111
 185÷111=1 余り74
 111÷74=1   余り37
 74÷37=2  余り0
 よって、最大公約数は37。


 単純に割り算を繰り返していけば最大公約数を求められますので、大きな素数を因数に持つ数同士の最大公約数を求める際にも、ストレスなく計算で求められます。


 便利な計算法ですが、「なぜ求まるか」が参考書には記載されていず、もやもやしていました。


 本書では、上記、最大公約数を求める計算を、正方形のタイルを用いて、縦185横851の長方形を作る問題に置き換えます。正方形の大きさをなるべく大きくとった時、正方形の1辺の長さは?という問題です。

  本書ではこれを上記のような図形に変換して説明しています。


 上記は「851÷185=4 余り111」の計算を図化していますが、この作業を繰り返すことにより、ちょうど正方形で「割り切れる」形である37✖37が求まります。逆に、この大きさの正方形で図形を埋めていけば、もともとの185✖851という長方形を埋めることができます。すなわち、この37が851と185の最大公約数になります。


 本書でのモットーが巻頭に記されていて、
 その2は、「始めから終わりまで同じ丁寧さ」
 その3は、「例から説明している」
 
 こんな感じのわかりやすい説明で、ガロア理論が理解できればいいな、、、というのは甘い考えかもしれませんが、まずは第一歩。