ユークリッドの互除法とかいうやつ

ユークリッドの互除法を最初に見たときは、正直イミフというか、何に使うんだよって感じで、いらねーと思ってたんですけど、思い返してみれば随分と馬鹿だったなあと思っています。

と、いうのも、フィボナッチ数列について調べていたとき、フィボナッチ数の隣り合う項は全て互いに素であるという命題をみつけて、(自分で証明できるかもしれないな)とか思い、証明を試みた際にふと思い出して、見事証明にたどりつけたからです。

それではユークリッドの互除法を、理解しましょう

ユークリッドの互除法とは、

ある自然数aとb (a > b)において、a÷bの余りをrとすると、aとbの最大公約数はbとrの最大公約数に一致する。

というもの。とりあえず例を見てみましょう。

適当に、12と34にしましょうか。この２つの最大公約数を知りたいとします。このときユークリッドの互除法より、34÷12=2 余り10だから、

34と12の最大公約数は12と10の最大公約数を考えればいいということになります。ここでまたユークリッドの互除法です。12と10の最大公約数は、12÷10=1 余り2 より10と2の最大公約数に一致するということです。10と2の最大公約数は2だから、結局12と34の最大公約数は2と分かります。少しわかりにくいですかねぇ

最大公約数とか書くのめんどいので、aとbの最大公約数を(a,b)と書くことにします。(gcd(a,b)って言う一般的な書き方もあるけど、それすら書くのめんどい。

もう少し簡単な例を挙げると、14と6とかにしましょう。この2つの数の最大公約数を知りたくてしょうがないとします。ユークリッドの互除法より、(14 , 6)は(6 , 14÷6の余り)であるから(14,6)=(6,2)です。(6,2)=(2,0)で(2,0)は2だから知りたかった(14,6)は2となります。

例示は理解の試金石とどっかの数学ボーイが言ってました。その通りです。例をたくさんやってみてください。必ず理解がすすみます。

それと、たくさんやってほしい理由はもう1つあって、そのうち最大公約数1とかいう組に出くわすと思います。この流れを知っておいてほしいというのもあるからたくさんやってください。

勘のいい人は気づいているかもしれませんが、最大公約数が1ってゆうのは互いに素ってことです。

まあ、当たり前ですね。最大公約数1ってことは共通する約数が1以外にないってことですから。

さらに勘のいい人は気づいてるかもしれませんが、この流れがさっき言ったフィボナッチ数列の命題に深く関わるいわば主役となる存在です。

あー言い忘れてましたけど、ユークリッドの互除法の証明はしません。

理由は2つあって、つまらないからという理由と、なんだかパッとしなくて証明した感じにならないから。という理由です。

どうしても気になる人は他のサイトなりを見てください。証明を理解するより、ユークリッドの互除法を理解してほしいので、完全に理解したなと思ってから証明を見るのを勧めます。

まあ、そんなこんなで書くことなくなりました。

あー、一応例題的なのを出しときます。

問題 1234と5678の最大公約数を求めよ。

答え

(5678,1234)=(1234,742)=(742,492)

=(492,250)=(250,242)=(242,8)=(8,2)=(2,0) 

よって2

((2,0)というのは0で割れないから定義できないのですが、ユークリッドの互除法の性質上(2,0)に行き着いた場合は最大公約数2と考えられます。)