ユークリッドの互除法とは？やり方をわかりやすく解説！

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

この用語の要点

ユークリッドの互除法とは、2つの自然数の最大公約数を求めるための古典的なアルゴリズムアルゴリズムある問題を解くための、明確に定められた手順。9世紀の数学者フワーリズミーの名がラテン語化され、算術の計算法を指す語を経てこの言葉になった。です。古代ギリシアの数学者ユークリッドが著した『原論原論（ストイケイア）古代ギリシアの数学者ユークリッドが著した数学書。定義・公準・共通概念から出発して命題を積み重ねる構成で、幾何学から数論までを体系化した全13巻。詳しく見る →』の中で紹介され、現在でも広く使われています。

この方法は、次の性質にもとづいています。

2つの自然数 a, b（a ≧ b）において、a を b で割った余りを r としたとき、a と b の最大公約数は、b と r の最大公約数に等しい。

a ＝ b × q ＋ r　のとき
（a と b の最大公約数）＝（b と r の最大公約数）

数を小さくしても最大公約数は変わりません。だから、割り算を繰り返して数を小さくしていけます。

たとえば252と105の最大公約数を求めると、

252 ÷ 105 ＝ 2 余り 42
105 ÷ 42 ＝ 2 余り 21
42 ÷ 21 ＝ 2 余り 0

余りが0になったときの「割る数」21が、252と105の最大公約数です。

「世界最古のアルゴリズム」とも言われ、アルゴリズムの教科書には必ずといっていいほど登場します。桁の多い数どうしでも短い手数で終わるので、コンピュータや暗号の分野でも使われています。

現在よく知られている互除法は割り算を使いますが、『原論』に書かれたもともとの形は、割り算ではなく引き算の繰り返しで、「相互差引」と呼ばれます。

手順はこうです。2つの数のうち、大きい方から小さい方を取り除く。これを繰り返すと、いずれ残された2数は等しくなります。最後に残った数が最大公約数です。

たとえば21センチのロープaと15センチのロープbで試してみましょう。

21 － 15 ＝ 6
15 － 6 ＝ 9
9 － 6 ＝ 3
6 － 3 ＝ 3

最後に3と3で等しくなりました。この3が21と15の最大公約数です。

この操作は、底辺a・高さbの長方形を、なるべく大きな正方形で敷き詰める問題としても説明できます。「a×bの長方形を大きな正方形で敷き詰める問題」は「(a－b)×bの長方形を敷き詰める問題」に置き換えられ、これをどんどん小さくしていくと、最後に敷き詰められる正方形の一辺が最大公約数になります。

「比の理論」を支える縁の下の力持ち

『原論』では、この相互差引から導かれる性質を土台にして、「数の比の理論」という体系が組み立てられています。

たとえば、2つの分数が等しいかどうかを判定するには、それぞれを約分して同じ既約分数になるかを調べればよいのですが、この「約分すれば一意的な形が得られる」という事実自体が、互除法の考え方から導かれます。

一見地味な「引き算（あるいは割り算）を繰り返すだけ」というこの手続きが、比や分数、さらには「aとbが互いに素で、aがbcを割り切るならaはcを割り切る」といった整数論の基本的な性質まで支える縁の下の力持ちになっています。この定理の奥深さは、そこにあります。

ポゥじい博士の見立て

おもしろいのは、『原論』では「量の比の理論」が「数の比の理論」より前に現れることじゃ。じゃが、理論ができ上がった順に書かれているとは限らんのじゃよ。

わしは、「数の比の理論」が先にあって、「量の比の理論」はその後に創られたと考えるのが自然じゃと思っておる。比を簡略化して既約な比を求める、つまり約分にあたる考え方のほうが先にできて、そこから理論が整えられていったのではないかのう。

由来となったユークリッドとはどんな人物か

あらゆる数学の基礎となる名著『原論』を著したことで知られ、「幾何学の父」とも称されます。『原論』は、当時知られていた幾何学や数論の知識を、定義・公理・命題・証明という論理的な順序で体系化した画期的な書物で、この構成方法は2000年以上にわたり数学教育と論理思考のモデルとして受け継がれてきました。