さて、ユークリッドとは実在する人物の名前ですが、ユークリッドの生涯については、詳しいことはほとんど分かっていません。紀元前３３０年に生まれて紀元前２７５年に死んだという説や、紀元前３６５年に生まれたという説などまちまちです。いずれにしても紀元前約３００年頃の人であろうということくらいは分かっています。彼は当時のエジプトの王であったプトレマイオスの招きに応じてアレクサンドリアに行き、そこで教授、著作、研究に専念したそうです。彼はそこで当時までに知られていたあらゆる数学のデータ収集をし、再検討を加えて整理しました。これが現在の数学でも絶大なる力を持っている『原論』という大著となりました。当時も数学の教科書として使用されていたようで、これに纏わる有名なエピソードがあります。

『原論』を教科書としてユークリッドから幾何学を学んでいたプトレマイオス王が、『幾何学をもっと簡単に学ぶ近道はないのか？』と質問したのに対して、『幾何学に王道なし』と答えたというのです。

この『原論』は、聖書に次ぐ大著として、１４８２年以来１０００種類以上の言語に翻訳されたものが出版されたといわれています。内容は、おおまかにいうと第１章〜第６章は｢平面幾何｣、第７章〜第９章は｢数論｣、第10章は｢無理数｣、第11、第12章は｢立体幾何｣、第13〜第15章は｢正多面体｣についてまとめています。以前には何とも思わなかったような物が、興味深い物として目に映ることをご期待して、この不思議な数の世界へご招待致したいと思います。

【公約数について】

　例えば、３０と４５の約数は、

３０の約数・・・１、２、３、５、６、１０、１５、３０
４５の約数・・・１、３、５、９、１５、４５

ですから、２つの約数のうち共通の｢１、３、５、１５｣の４つの数字が３０と４５の公約数となります。
また、公約数のうち最大の約数を最大公約数(G.C.M.ともいう。Greatest Common Measureの略）といい、この場合１５となります。ここで、最大公約数を求めるときに、いまのように１つ１つ約数を取り上げて比べていくのではなく、もっと簡単に求める方法があります。その方法がユークリッドの互除法なのです。

【ユークリッドの互除法について】

　これは前述の「原論」の第７章にやや異なった形で述べられていますが、それはユークリッドよりも１００年ほど前にすでに発見されていたと伝えられています。

【ユークリッドの互除法】

２つの整数aとbについて、

a をb で割った余りをr1 　(b >r1)
b をr1で割った余りをr2 　(r1>r2)
r1をr2で割った余りをr3 　(r2>r3)
　　・・・・・・・・・・
としていくと、r1>r2>r3･････≧0 となって余りはいつか0になる。

そこで余りが○>□となって、○が□で割り切れたとすると、□が最大公約数である。

もうちょっと一般化していうと、２つの整数aとbがあり、aがbで割り切れないとき、kを任意の整数として、aとbの最大公約数はa+bkとbの最大公約数に等しいということです。

それでは、６０と１６８の最大公約数をこの方法で求めてみましょう。

１６８÷６０＝２ 余り ４８
　６０÷４８＝１ 余り １２
　４８÷１２＝４ 余り 　０ →　４８が１２で割り切れるので、１２が６０と１６８の最大公約数となる。

ユークリッドの互除法を使うと、いつか必ず割り切れて、そのときの割った数が最大公約数となります。
（ユークリッドの互除法はＮ桁の数に対して５Ｎ回以内で終了することがわかっています。）

でも、なぜこんなにも簡単に最大公約数が求まるのか不思議ですね？それでは、互除法の原理を証明してみましょう。高校の参考書などに載っている互除法の原理はだいたい以下のように解説されています。

【互除法の原理の証明】

２つの整数aとbの最大公約数をＧとおくと、a=a'Ｇ，b=b'Ｇ(a'とb'は互いに素(注))とおける。
（注；互いに素とはa'とb'の公約数が1以外にはないということ。）
同様に、bとrの最大公約数の最大公約数をＧ'とおくと、b=b''Ｇ'，r=r'Ｇ'となる。

このことを以下の�@〜�Bで利用して考えてみる。

�@ aをbで割ったときの商をq，余りをrとすると、a=bq+r (0≦r<b)と表せる。この式をrについて解くと
　 r=a-bq となる。
　ここで、２つの整数aとbは、a=a'Ｇ，b=b'Ｇとおけるから、
　 r=a'Ｇ-b'Ｇq=(a'-b'q)Ｇと表せる。

　すなわち、r=r'Ｇ'であることから、ＧはＧ’の約数である。

�A b=b''Ｇ'，r=r'Ｇ'より、a=bq+r=b''Ｇ'q+r'Ｇ'=(b''q+r')Ｇ'となる。

　すなわち、a=a'Ｇ であることから、Ｇ’はＧの約数である

�B �@と�Aが同時に成り立つので、Ｇ＝Ｇ’である。

以上のことをもう少し簡単に表現すると、aをｂで割ったときの余りrは、aとbの最大公約数を因数にもつ。言いかえると

『aとbの最大公約数はbとrの最大公約数と考えてよい。』ことがわかります。

この証明は、いわゆる｢必要十分条件｣という考え方から導かれる証明法で、なかなか生徒に説明して理解させるのに苦労します。（生徒はこのような論述形式の証明をいたって嫌う傾向にあります。）しかも、aやらbやらたくさんの文字を使用するので、読むのさえ苦労することでしょう。

さて、これで終わってしまっては、今回のテーマである｢かんたんユークリッドの互除法｣とは言い難いですよね？！実は図形を利用することで、ユークリッドの互除法を小学生にも理解できるように説明できる素晴らしい方法があるのです。

【かんたんユークリッドの互除法】

【四角形と公約数の関係】

　さて、もう一度先ほどの６０と１６８の最大公約数を求める問題を考えてみましょう。

　右の図をご覧下さい。縦が６０、横が１６８の横長の長方形から、短い方の辺である、６０を１辺とする正方形をできるだけ多く切り取っていきます。（図では２個の正方形が切り取れることになる。）
すると最後に縦が６０、横が４８の長方形が残ることになります。
ちょっとここで前述の １６８÷６０＝２ 余り ４８ という式の意味を考えてみましょう。
１６８÷６０とは、１辺が６０の正方形を何個切り取れるかを計算していることになります。その結果、商が２、余りが４８というわけですから、縦が６０、横が１６８の横長の長方形から１辺が６０の正方形が２個とれて、最後に縦が６０、横が４８の長方形が残るというわけです。

　それでは次に、 ６０÷４８＝１ 余り １２ と ４８÷１２＝４ 余り ０ の式の意味するところも同様に考えてみましょう。右の図をご用意致しました。考え方は先ほどと同じですので、じっくりご覧いただければすぐに理解できることと思います。

以上のことをまとめてみましょう。長方形から短い方の辺を１辺とする正方形を切り取る操作を全部で３回行った結果、１辺が１２の正方形で終了ということになったわけです。
すなわち縦が６０、横が１６８の長方形を１辺が１２の正方形で敷き詰めることができることと、１２が６０と１６８の最大公約数となることが同じであるということが理解できたと思います。

それでは３００７と１６４９の最大公約数をユークリッドの互除法を使って求めてみましょう。！！とてもじゃないけれど最初にしたように２つの数のそれぞれの約数を並べて比較するなんて大変ですよね？ユークリッドの互除法（先人の知恵）のありがたさをつくづく感じてしまいます．．．

（答えは９７となります。）

【最後に】

　ユークリッドの互除法は、最大公約数を求めるためだけのものではありません。例えば次のような問題がユークリッドの互除法の考え方で解くことができます。

１円玉、１０円玉、５０円玉があわせて１００枚あり、その総額は５００円である。このとき１円玉、１０円玉、５０円玉はそれぞれ何枚あるか。

（答えは１円玉 ６０枚、１０円玉 ３９枚、５０円玉 １枚となります。）

さて、１円玉をｘ枚、１０円玉をｙ枚、５０円玉をｚ枚として連立方程式をたてると
ｘ＋ｙ＋ｚ＝１００・・・�@
ｘ＋１０ｙ＋５０ｚ＝５００・・・�Aで、�@からｚ＝１００−ｘ−ｙを�Aに代入して４９ｘ＋４０ｙ＝４５００を得ます。ところがこれだけだと、生徒はだいたい次の２つの解答をします。

【解法１】

ｙ=１１２＋（２０−４９ｘ）/４０と０≦ｘ＜９２から、ｘが整数になるときをｘ=０〜９１の９２通り代入してみつける。

【解法２】

ある整数解（ｘ,ｙ）=（ｍ,ｎ）がみつかったならば、すべての整数解を（ｘ,ｙ）＝（ｍ＋４０ｋ,ｎ−４９ｋ）と表せる。（ここで、ｍ,ｎ,ｋは整数）
ということは、整数解が存在するならばｍ=０〜３９のうちいずれかであるような解が必ず存在することになるから、ｍの値を４０通り代入してみつける。ということで、【解法１】よりは少なくて済みます。

　以上のように、パソコンでもあればプログラムを組んで全部代入するということも可能でしょうが、そうでなければ面倒くさくてやる気がしませんよね？このような方程式を不定方程式といいますが、ユークリッドの互除法を使えば比較的簡単に解くことができます。

しかしながら今回は敢えて解説しないでおきます。というのも｢四角形と公約数の関係｣という主題からはずれてしまうことと、自ら調べて発見する喜びというものもありますので、もし興味を持たれた方は図書館などへいって関連文献を調べて下さいね。