用語集
拡張ユークリッドの互除法かくちょうゆーくりっどのごじょほう
互除法 の 計算を逆にたどり、 ax + by = gcd(a,b) を 満たす 整数 x, y を 求める 方法。
互除法 の 計算を逆にたどり、 ax + by = gcd(a,b) を 満たす 整数 x, y を 求める 方法。
拡張ユークリッドの互除法とは、ユークリッドの互除法の各ステップの式を下から逆にたどることで、 を満たす整数（ベズーの等式の解）を具体的に求める方法です。
| 手順 | 内容 |
|---|---|
| 1 | 互除法で余りの式を順に書き出す |
| 2 | 余り に変形 |
| 3 | 下から代入して を の形にする |
たとえば は、 と逆算でき、 が得られます。
試験では 1次不定方程式 の特殊解を作る標準手段。互除法の式を一度ぜんぶ書いてから、下の式から順に代入していくのがコツ。