拡張ユークリッド互除法とは、ユークリッドの互除法で gcd(a,b) を求めたあと、その割り算の式を下から逆にたどることで、ax+by=gcd(a,b) を満たす整数x,y(ベズーの等式の解)を求める方法です。
| 手順 | 内容 |
|---|
| 1 | 互除法で gcd を求め、各ステップの式を残す |
| 2 | 余り =a−bq の形に変形する |
| 3 | 下の式から順に代入し gcd=ax+by に直す |
たとえば gcd(11,4)=1 で、11=4⋅2+3, 4=3⋅1+1 より 1=4−3=4−(11−4⋅2)=11⋅(−1)+4⋅3 となり、(x,y)=(−1,3) が得られます。
試験では 1次不定方程式 ax+by=c の特殊解を1組見つける標準手法。互除法の式を「余り=…」に直してから逆代入するのがコツ。