方針
\gcd(a, b) = \gcd(b, r)（a = bq + r）を繰り返し、余りが 0 になった直前の値が \gcd である。そのあと逆向きに代入（拡張互除法）して \gcd(a,b) = ax + by の形に表現する。
厳密な説明
1. なぜ余りへ落としてよいか
a = bq + r のとき、a と b の共通約数 d は r = a - bq も割るので d は b と r の共通約数でもある。逆も同様に成立するので
\gcd(a, b) = \gcd(b, r)
余りへ落としても共通約数の集合が変わらない—これが互除法の核心である。
2. ユークリッドの互除法（例：\gcd(84, 30)）
| ステップ | 割り算 | 余り |
|---|
| 1 | 84 = 30 \times 2 + 24 | r = 24 |
| 2 | 30 = 24 \times 1 + 6 | r = 6 |
| 3 | 24 = 6 \times 4 + 0 | r = 0 → 終了 |
\gcd(84, 30) = 6。
3. 拡張互除法：\gcd を ax+by の形へ
ステップ 2 から逆向きに代入する：
6 = 30 - 24 \times 1
ステップ 1 より 24 = 84 - 30 \times 2 を代入：
6 = 30 - (84 - 30 \times 2) = 3 \times 30 - 84 = (-1) \times 84 + 3 \times 30
したがって x = -1, y = 3 が一つの解である。
4. 一次不定方程式の可解条件
ax + by = c が整数解を持つための必要十分条件：
\gcd(a, b) \mid c
証明（必要条件）：d = \gcd(a, b) とすると a = da', b = db' なので ax + by = d(a'x + b'y) は必ず d の倍数。
証明（十分条件）：c = dk かつ d = ax_0 + by_0 なら c = a(kx_0) + b(ky_0)。
一般解：一つの解 (x_0, y_0) があれば全解は
x = x_0 + \frac{b}{d} t, \quad y = y_0 - \frac{a}{d} t \qquad (t \in \mathbb{Z})
5. mod 逆元との関係
ax \equiv 1 \pmod n が解けることと \gcd(a, n) = 1 は同値である。これは ax + ny = 1（一次不定方程式）が解けることと同値だからである。互除法は mod 逆元の計算（中国剰余定理の中核）を支える。
複数の解法
方法 1（素因数分解）：a, b が小さければ素因数分解で \gcd を直接計算できる。ただし大きな数では非効率。
方法 2（互除法）：一般的手法。O(\log \min(a,b)) ステップで終了する。
方法 3（行列表現）：拡張互除法の係数を 2 \times 2 行列の積として管理する方法。実装で頻用される。
最終形
\boxed{\gcd(a,b) = \gcd(b,r) \quad (a = bq + r)}
\boxed{ax + by = c \text{ が[整数解/せいすうかい]を[持/も]つ} \iff \gcd(a,b) \mid c}
\boxed{x = x_0 + \frac{b}{d}t,\quad y = y_0 - \frac{a}{d}t \quad (t \in \mathbb{Z})}