【数学】ユークリッドの互除法で何で最大公約数が求まるのかという話 │ コジマノテック

1. はじめに
2. ユークリッドの互除法で何ができる？
3. 最大公約数に関する定理
4. 原理
5. 証明
6. さいごに

はじめに

コジマです。

ユークリッドの互除法って聞いたことある人多いと思います。
単純なアルゴリズムである故に、プログラミングを勉強する過程で実装した経験がある人も
いるのではないでしょうか？

ユークリッドの互除法を使うことで何で最大公約数が求まるんだ？
って話をしていきたいと思います。

ユークリッドの互除法で何ができる？

これは先にやって見せた方がわかりやすいと思うので簡単に例を挙げたいと思います。

（1回矢印引きそびれたけど、まあわかるよね…）

このように2つの数を割った余りでまた割って…
という作業を続けていくと最後余りが0になります。

そうすると、その一段階手前の余りが
最初の2数の最大公約数になる(求めることができる)
というのがユークリッドの互除法です。

大きい数同士の最大公約数を求めるのは大変ですが、
ユークリッドの互除法を使えばアルゴリズムで探すことができます。

ユークリッドの互除法には、以下に示す最大公約数に関する定理を使用します。

最大公約数に関する定理

定理としてはこれだけです。

超大事なんですけど、ちゃんとした名前付いてないんですよね〜。
割り算と最大公約数の関係といったところでしょうか。
割と文献によってまちまちです。

数式ばっかでちんぷんかんぷんの人のために日本語で説明。
a,bは自然数。(便宜的にa≧bとします。)
aをbで割った商をq,余りをrとした時にa=bq+rと書くことができます。
このとき、aとbの最大公約数とbとrの最大公約数が等しくなります。

gcd(a,b)というのは、「aとbの最大公約数」という意味です。

この定理の便利なところは、先ほどの例や以下の原理でも示しますが、
再帰的かつ有限回の操作で使用可能なところです。
要するにアルゴリズムで処理が可能になるのです。

原理

例に挙げたところを数式で表現してみようと思います。

式で見るとややこしくなるかと思いますが、言葉で書けばわかりやすくなるかと思います。

aをbで割った余りがr => (aとbの最大公約数) = (bとrの最大公約数)
bをrで割った余りがr_1 => (bとrの最大公約数) = (rとr_1の最大公約数)
rをr_1で割った余りがr_2 => (rとr_1の最大公約数) = (r_1とr_2の最大公約数)
・
・
・
r_(i-2)をr_(i-1)で割った余りがr => (r_(i-2)とr_(i-1)の最大公約数) = (r_(i-1)とr_iの最大公約数)
r_(i-1)をr_iで割った余りが0 => (r_(i-1)とr_iの最大公約数) = r_i

ユークリッドの互除法を利用するとこのように再帰的に処理を行うことができます。

aをbで割った余りは必ずbより小さくすることができるので、
同じ操作を繰り返せば最終的に余り0となります。

最終的に
(aとbの最大公約数)=r_i
と求まります。

これがaとbの最大公約数が求まる原理です。

証明

i)aとbの共通の約数(公約数)がrの共通の約数である
ii)bとrの共通の約数がaの共通の約数である
この2つを示すことができれば、必要十分になります。
上記2条件から(aとbの共通の約数)=(bとrの共通の約数)となり、
最大公約数も等しい。
よって、gcd(a,b) = gcd(b,r)
となることを示す。

方針としてはこのようになります。

実際の証明はこちら。

補足)d|aは「d divides a」と読みます。「dはaの約数」という意味です。