C言語で学ぶ拡張ユークリッドの互除法：GCDとベズー係数の求め方

この記事では、C言語による拡張ユークリッドの互除法（Extended Euclidean Algorithm）の実装方法を解説します。拡張ユークリッドの互除法は、通常のユークリッドの互除法と同じように最大公約数（GCD）を求められるだけでなく、次の等式を満たす整数係数 x と y も同時に求められる点が大きな特徴です。

𝑎𝑥 + 𝑏𝑦 = gcd(𝑎, 𝑏)

このような形の等式は「ベズーの等式」と呼ばれ、係数 x と y は「ベズー係数」とも呼ばれます。このアルゴリズムでは、gcd(a, b) の値を gcd(b mod a, a) という再帰呼び出しによって順に更新しながら計算を進めていきます。

処理の流れを理解するために、まず擬似コードでアルゴリズムを確認しましょう。

アルゴリズム

EuclideanExtended(a, b, x, y)

begin
    if a is 0, then
        x := 0
        y := 1
        return b
    end if
    gcd := EuclideanExtended(b mod a, a, x1, y1)
    x := y1 – (b/a)*x1
    y := x1
    return gcd
end

ポイントは、再帰の戻り時に得られた係数 x1 と y1 を使って、現在のレベルでの係数を x = y1 − (b/a)・x1、y = x1 として更新するところです。これにより、各再帰段階でベズーの等式が成り立つように係数が組み立てられていきます。

C言語での実装例

以下は、上記のアルゴリズムをC言語で実装したサンプルプログラムです。係数 x と y はポインタ経由で呼び出し元に返されます。

#include <stdio.h>
int EuclideanExtended(int a, int b, int* x, int* y) {
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }
    int xtemp, ytemp; // 再帰呼び出しの結果を格納する変数
    int res = EuclideanExtended(b % a, a, &xtemp, &ytemp);
    *x = ytemp - (b / a) * xtemp;
    *y = xtemp;
    return res;
}
int main() {
    int x, y;
    int a = 60, b = 25;
    int res = EuclideanExtended(a, b, &x, &y);
    printf("gcd(%d, %d) = %d", a, b, res);
}

実行結果

gcd(60, 25) = 5

この例では、a = 60、b = 25 に対して GCD である 5 が正しく求められています。実際、このときの係数を使うと 60x + 25y = 5 を満たす整数の組（x = −2, y = 5 など）が得られ、ベズーの等式が成立していることが確認できます。

応用：モジュラー逆元の計算

拡張ユークリッドの互除法は、単なるGCD計算にとどまらず、モジュラー逆元の計算にも利用されます。ax + by = gcd(a, b) において、a と m が互いに素（gcd(a, m) = 1）であれば、ax ≡ 1 (mod m) を満たす x が a の mod m における逆元となります。これはRSA暗号などの公開鍵暗号や、競技プログラミングにおける合同式の計算で頻繁に使われる重要なテクニックです。