昨日まで，大学入試の問題を素材にしていましたので，
今日は趣向を変えて小学生にも役に立つ話題を．
問題はお茶の水女子大付属の問題です．
問題 ２つの整数1271と1517の最大公約数を求めなさい．
単なる計算問題と思うなかれ．ためしに計算してみると，
えらく手間のかかる作業になってしまいます．
そこで登場するのが，「ユークリッドの互助法」ですが，
その前に，この問題は１(2)ですので，(1)を紹介します．
(1) ２つの異なる自然数A，Bがある．A，Bが３の倍数であるとき，
A-Bも３の倍数になることを証明しなさい．
合同式の洗礼？を受けた皆さんなら，これは当たり前ですね．
この(1)は文字式でも簡単に証明できます．
つまり，
A=3a , B=3b とすると，
A-B=3a-3b=3(a-b) より， A-Bも３の倍数．
こんな手順です．
さて，この(1)をどうやって(2)に活かすか，と言いますと，
1517-1271=246 となりますが，このことは，
「1517の公約数と1271の公約数は，1271と246の公約数に等しい」
と言うことを利用します．
つまり，1517≡1271 [mod n ] …①
ならば，1517-1271≡1271-1271≡0 となりますので，
①のnを1517と1271の公約数とすれば，
1517-1271=246も，nで割り切れる数である，と言うことが分かります．
よって，1517と1271の間の関係を考えるのではなく，
1271と246の関係を考えた方が楽だ，というのが基本的な発想です．
では，1271と246の関係を考えるときには，どうすればよいでしょうか．
…同じ作業をすればよいですね．
1271-246=1025 となりますので， 次は1025と246
1025-246=779 ですので， 次は779と246 …，と続けます．
ただ，延々と同じ引き算をするのは面倒なので，
1271÷246＝５余り41を利用します．つまり，この式からは
1271-5×246=41 と言う関係式が導かれますので，
「1271から246を5回引けば，41になる」と言うことが分かります．
これで，何度も同じ数を引く手間が省けました．
同じように，246と41の関係を考えればよいのですが，
246÷41=６ と246は41で割り切れてしまいます．
と言うことは，246は41(この数は素数です)の倍数となります．
さらに，1271-246×5=41が成り立つことから，
1271も41の倍数であり，1517=1271+246より，
1517も41の倍数です．
よって，1517と1271の最大公約数は41であることが分かります．
(なぜ，「最大」かというと，
それ以前に公約数が出てこなかったからです)．
ちなみに1517＝41×37
1271＝41×31
となり，どちらも比較的大きな素数同士の積となっています．
ここまでに実行した作業が「ユークリッドの互助法」です．
具体的な作業としては，公約数を考えるときは，お互いを
割り算しあって，その余りについて考えていけばよい，
というものでした．
ためしに別の数でもやって見ましょう．
1591と731の公約数を考えます．
1591÷731＝２余り129 ①
731÷129＝５余り86 ②
129÷86＝１余り43 ③
86÷43＝２ で割り切れるので， ④
1591と731の最大公約数は43です．
作業の意味を確認しましょう．
①は 1591－731×2＝129ですので，
1591と731と129は同じ数で割り切れる，と言うことが分かります．
同様に②は 731-129×5＝86より，
731と129の公約数は，129と86の公約数でもある，と分かります．
以下，③，④と同じ作業ですが，
④で， 86=43×2 で余りがなくなります．
ということは，86は43の倍数であることが一目で分かりますので，
③より，86と129も43の倍数，②より731も43の倍数，と分かります．
(②の式は731-43×3×5=43×2ですので，731=43×(15+2)となります)
最後に①に遡れば，1591も43の倍数ですので，
めでたく，1591と731の最大公約数は43であることが分かりました．
さて，このようなケースはどうなりますでしょうか．
問題 1591と1457の最大公約数を求めよ．
作業をしましょう．
1591÷1457＝1余り134
1457÷134 ＝10余り117
134÷117 ＝1余り17
117÷17 ＝6余り15
17÷15 ＝1余り２
15÷２ ＝７余り1
2÷1 ＝２ で割り切れました．
つまり，1で割って割り切れたので，最大公約数は１となります．
実は1591＝43×37
1457＝47×31 ですので，
この二つの数は「互いに素」となります．
このような場合にも，最後に最大公約数１を答えてくれるわけですから，
互助法の威力の程が伺えます．
ユークリッドはヘレニズム時代の偉大な数学者(らしい)で，
『(幾何学)原論』の著者として知られています．
「ユークリッド幾何学」とか「ユークリッド平面」に名前が残っていますね．
有名なエピソードはいくつもあるのですが，
「学問に王道なし」との発言とも結び付けられています．
(王様が「幾何学は有益だが，手間がかかりすぎる．
もっと楽にこれを身につける方法はないのか」と質問してきたときの
答えである，とものの本には載っています)．
「学問に王道なし」とは至言ですね．
自分があれこれ学べば学ぶほど，この言葉の重みを実感する毎日です．