ユークリッドアルゴリズムは二つの整数$a$と$b$の最大公約数（GCD）だけを計算するが、拡張版では$a$と$b$でGCDを表す方法も見出す、つまり

$a \cdot x + b \cdot y = \gcd(a, b)$$

ここで重要なことは、このような表現は必ず見つかることです。例えば、$gcd(55, 80) = 5$ですから、$55$と$80$の項との線形結合として$5$を表現できることに注意してください。 55 \cdot 3 + 80 \cdot (-2) = 5$

この問題のより一般的な形式は、線形ディオファントス方程式の記事で説明されています。3333>

Algorithm

この節では、$a$と$b$のGCDを$g$と表記することにする。

元のアルゴリズムの変更は非常に簡単で、アルゴリズムを思い出すと、$b = 0$と$a = g$で終わっていることがわかります。このパラメータに対して、$g \cdot 1 + 0 \cdot 0 = g$という係数が簡単に求められます。

この係数$(x, y) = (1, 0)$ から始めて、再帰的呼び出しを逆算していけばいいのです。あとは、$(a, b)$ から $(b, a \bmod b)$ へと移行する間に、係数 $x$ と $y$ がどう変化するかを考えればよいのです。

ここで、$(b, a \bmod b)$ の係数 $(x_1, y_1)$ が見つかったとします：

$b \cdot x_1 + (a \bmod b) \cdot y_1 = g$

そして $(a, b)$ のペア $(x, y)$ も求めたいのですが、これはどうすればよいでしょうか？

$ a \cdot x + b \cdot y = g$$

ここで、$a \bmod b$を次のように表すことができる：

$ a \bmod b = a – \leftlfloor \frac{a}{b} \rightrfloor \cdot b$$

この式を$(x_1, y_1)$の係数式に代入すると、次のようになる。

$ g = b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a – \leftloor \frac{a}{b} \rightrfloor \cdot b) \cdot y_1$

そして項の整理をすると。

$g = a \cdot y_1 + b \cdot \left( x_1 – y_1 \left \right)$$

$x$と$y$の値を求めました。

$$begin{cases}x = y_1 ♪y = x_1 – y_1 ♪dot ♪left ♪lfloor ♪frac{a}{b} である。 \rightrfloor end{cases} $$

実装

int gcd(int a, int b, int& x, int& y) { if (b == 0) { x = 1; y = 0; return a; } int x1, y1; int d = gcd(b, a % b, x1, y1); x = y1; y = x1 - y1 * (a / b); return d;}

上の再帰的関数はGCDと係数の値をxとy（関数に参照渡し）に返す。

この拡張ユークリッドアルゴリズムの実装は負の整数に対しても正しい結果を返す。

反復バージョン

拡張ユークリッドアルゴリズムを反復的に書くこともできます。再帰を避けるので、再帰的なものより少し速く実行できます。

int gcd(int a, int b, int& x, int& y) { x = 1, y = 0; int x1 = 0, y1 = 1, a1 = a, b1 = b; while (b1) { int q = a1 / b1; tie(x, x1) = make_tuple(x1, x - q * x1); tie(y, y1) = make_tuple(y1, y - q * y1); tie(a1, b1) = make_tuple(b1, a1 - q * b1); } return a1;}

変数 a1 と b1 をよく見てみると、通常のユークリッドアルゴリズムの反復バージョンとまったく同じ値を取っていることに気がつくと思います。

なぜこのアルゴリズムが正しい係数を計算するのかを見るには、次の不変量がいつでも（whileループの前と各反復の終わりで）成り立つことを確認します：$x \cdot a + y \cdot b = a_1$ と $x_1 \cdot a + y_1 \cdot b = b_1$ です。この2つの式が最初に成立していることは容易に確認できる。また、ループの反復で更新してもこれらの等式が有効であることが確認できる。

最後に $a_1$ には GCD が入っているので、 $x \cdot a + y \cdot b = g$ となり、必要な係数が求まったことになります。

さらに最適化して、変数 $a_1$ と $b_1$ を取り除き、 $a$ と $b$ だけ再利用してもよいでしょう。しかし、そうすると不変量について議論する能力が失われます。

練習問題

• 10104 – ユークリッド問題
• GYM – (J) Once Upon A Time
• UVA – 12775 – Gift Dilemma

.