最大公約数とユークリッドの互除法

最大公約数

0 ではない、いくつかの自然数 `a, b, cdots` の共通の約数を、これらの整数の公約数という。 `a, b, cdots` のなかには、これら公約数のなかで最大のものがある。これを、 `a, b, cdots` の最大公約数という。最大公約数はエスペラントでは plej granda komuna divizoro といい、 頭文字語の PGKD で表す。英語では greatest common divisor といい、頭文字語の GCD で表す。

ユークリッドの互除法

ユークリッドの互除法（エス : Eŭklida algoritmo、英 : Euclidean algorithm ）は、 二つの自然数の最大公約数を効率よく求めるアルゴリズムである。アルゴリズムは、 怪奇な再帰 - ユークリッドの互除法を参照のこと。

拡張互除法

ユークリッドの互除法は自然数 `a` と `b` の最小公倍数 `d` を求めるものであったが、 これを拡張して最小公倍数 `d` だけでなく、次の等式を満たす `x, y, d`

実装は、「飯高茂 : 環論、これはおもしろい」に基づく。概略は次のとおりである。

1. 3 次ベクトル `v_i (i = 0, 1, 2, cdots)` の初期値を次で定義する。
   `v_0 = (1, 0, a), v_1 = (0, 1, b), v_2(1, q_1, -r_1).`
   ただし、`q_1, r_1` はそれぞれ `a` を `b` で割った商および余りである。
2. `h = 2` とおく。
3. `v_h` の第 3 成分が 0 であれば 5. に行く。
4. `v_(h-1)` の第 3 成分を `v_h` の第 3 成分で割った商を `q` とし、`v_(h+1) = v_(h-1) - qv_h` を計算して `h = h+1` とし、3. に戻る。
5. `v_(h-1) = (x, y, d)` とするとこれが求める `d, x, y` である。

実装は、3 行 3 列の 2 次元配列 v[3][3]を用いている。を用いている。初期状態は、 `v[0] = [1, 0, a], v[1] = [0, 1, b], v[2] = [1, q_1, -r_1]` と忠実に実装している。 4. の処理で、h = h+1とするとき、`v[1] - qv[2]` を配列の map メソッドを用いて計算して、 配列 v の push メソッドでこの v の末尾にベクトルを追加し、v[3] とする。 その直後の `v` の先頭の要素 `v[0]` を配列 v の shift メソッドで削除するので、 `v[1]->v[0], v[2]->v[1], v[3]->v[2]` となる。以下は v[2][2] が 0 となるまでループを繰り返す。

ほかにも、「奥村晴彦 : C 言語による標準アルゴリズム」の合同式の項や、 「山﨑圭次郎:基礎代数」にも同様のアルゴリズムがある。

参考文献

• 飯高茂 : 環論、これはおもしろい
• 奥村晴彦 : C 言語による標準アルゴリズム
• 山﨑圭次郎 : 基礎代数

まりんきょ学問所 ＞ JavaScript 手習い ＞ 最大公約数とユークリッドの互除法