C++で拡張ユークリッドの互除法を実装する方法

拡張ユークリッドの互除法(Extended Euclidean Algorithm)は、2つの整数の最大公約数(GCD)を求めるためのもう一つの手法です。通常のユークリッドの互除法と異なり、ベズーの等式 ax + by = gcd(a, b) を満たす係数 x と y を同時に求められる点が大きな特徴です。モジュラ逆数の計算などへの応用も可能で、コンピュータプログラムにおいて非常に効率的な手法として知られています。

アルゴリズムの流れ

拡張ユークリッドの互除法は、再帰呼び出しを利用して以下の手順で実装します。

開始
   変数 a、b、x、y を宣言する
   gcdExtended(int a, int b, int *x, int *y)
   もし (a == 0) ならば
      *x = 0;
      *y = 1;
      return b;
   結果を格納するための2つの変数を用意する
   再帰呼び出しの結果を使って x と y を更新する
終了

C++サンプルコード

#include <bits/stdc++.h>
using namespace std;
int gcdExtended(int a, int b, int *x, int *y) {
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }
    int x1, y1;
    int gcd = gcdExtended(b % a, a, &x1, &y1);
    *x = y1 - (b / a) * x1;
    *y = x1;
    return gcd;
}
int main() {
    int x, y;
    int a = 35, b = 15;
    cout << "gcd " << gcdExtended(a, b, &x, &y);
    return 0;
}

実行結果

gcd 5

アルゴリズムの仕組み

このアルゴリズムのベースケースは a == 0 のときです。gcd(0, b) = b であり、0 × 0 + 1 × b = b が成り立つため、x = 0、y = 1 として b を返します。

再帰呼び出しから戻る際には、gcd(a, b) = gcd(b % a, a) という関係を利用します。b % a = b - (b / a) × a を代入して整理すると、次の更新式が導かれます。

*x = y1 - (b / a) * x1;
*y = x1;

このプログラムでは a = 35、b = 15 としており、実行すると gcd(35, 15) = 5 が出力されます。このとき x = 1、y = -2 が求まり、35 × 1 + 15 × (-2) = 5 が実際に成り立つことが確認できます。