# 拡張ユークリッドの互除法

## 拡張ユークリッドの互除法とは？
拡張ユークリッドの互除法とは、競技プログラミングでも用いられるアルゴリズムで、次の方程式の解 $(x, y)$ を求めることができる。

$$
\begin{equation} ax + by = c \tag{1}
\end{equation}
$$

アルゴリズムの説明の前に、上の方程式について少し考えてみよう。
自然数 $a, b, c$ が与えられたとき、方程式 $(1)$ に整数解 $(x, y)$ が存在するのはどのような場合なのだろうか？

いくつか具体例を考えてみる。 $a = 10, b = 4, c = 2$ のとき、方程式 $10x + 4y = 2$ は解 $x = -1, y = 3$ を持つ。しかし、 $a = 10, b = 4, c = 1$ のとき、方程式 $10x + 4y = 1$ は整数解 $(x, y)$ を持たない。

実は、方程式 $(1)$ に整数解が存在する条件は $c$ が、 $a$ と $b$ の最大公約数 $g$ の倍数になることである。実際、 $ax + by$ は $g$ の倍数となるため、解が存在するには $c$ が $g$ の倍数にならなければならないことがわかる。

## 拡張ユークリッドの互除法のアルゴリズム
ここから拡張ユークリッドのアルゴリズムについて述べる。
拡張ユークリッドの互除法アルゴリズムは、 自然数 $a, b$ が入力されたとき、
$$
\begin{equation}
ax + by = g \tag{2}
\end{equation}
$$ の整数解 $(x, y)$ を返すものである。

このアルゴリズムにはユークリッドの互除法に似たアイデアが使われている。
$a = q \cdot b + r$ と整数 $q, r\; (r < b)$ を用いて表せるので、
$ax + by = (qb + r)x + by = b(qx + y) + rx$ となる。よって、$x' = qx + y,\: y' = x$ とおくと、
$$
\begin{equation}
bx' + ry' = g \tag{3}
\end{equation}
$$ と $ax + by = g$ に似た形の方程式が得られた。よって、方程式 $(3)$ の整数解 $(x', y')$ が得られれば、それを $x' = qx + y,\: y' = x$ つまり $x = y',\: y = x' - qy'$ に代入することで $ax + by = g$ の整数解 $(x, y)$ が得られる。

方程式 $(3)$ の整数解は常に存在するだろうか？ 実はこれは常に存在する。なぜなら、最大公約数の性質から $gcd(a, b) = gcd(b, r)$ であり、前に行った方程式 $(1)$ の存在についての議論から方程式 $(3)$ は整数解を持つからである。

方程式 $(2)$ から $(3)$ へ変換することで、 $b$ と $r$ というより小さなサイズの問題に帰着できるのである。また、この変換をユークリッドの互除法と同じように繰り返すことで、いずれ
$$
\begin{equation}
gx + 0 \cdot y = g
\end{equation}
$$ という形の方程式が得られる。この方程式の整数解は $(1, 0)$ と簡単に求められる。あとはこの解から1つ前の方程式の解を求めて... とやっていけばいずれ求めたかった、方程式 $(2)$ の整数解が得られる。これが拡張ユークリッドの互除法のアルゴリズムである。

## アルゴリズムを具体例に適用してみる
具体例として$a = 10,\: b = 4$ に対してアルゴリズムを適用して $10x + 4y = 2$ の整数解を求めてみる。
$$
\begin{align}
10x + 4y &= 2 \\
4(2x + y) + 2x &= 2 \\
4x' + 2y' &= 2 \\
2(2x' + y') + 0 \cdot x' &= 2 \\
2x'' + 0 \cdot y'' &= 2
\end{align}
$$
となる。ただし、$x' = 2x + y,\: y' = x,\: x'' = 2x' + y',\: y'' = x'$ とおいた。
$x'' = 1,\: y'' = 0$ より、$x' = 0,\: y' = 1$ が得られ、これを使って求めたかった解 $x = 1,\: y = -2$ が得られる。

## アルゴリズムの実装例
最後に、拡張ユークリッドの互除法アルゴリズムのPythonでの実装例を紹介する

def extendedGCD(a, b):
    if b == 0:
        return (1, 0)
    
    q = a // b
    r = a % b
    x, y = extendedGCD(b, r)
    return (y, x - q*y)