ユークリッドの互除法
いよいよというか、遅ればせながら、上記左の「ガロア理論の頂を踏む」(石井俊全著)に着手。本購入以来、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は、「例から説明している」
こんな感じのわかりやすい説明で、ガロア理論が理解できればいいな、、、というのは甘い考えかもしれませんが、まずは第一歩。
このブログへのコメントは muragonにログインするか、
SNSアカウントを使用してください。