導入
拡張 Euclid アルゴリズムは Euclid アルゴリズムの変形で、2 つの整数aとbから、それらの最大公約数 (PGCD) だけでなく、それらの係数のペアの 1 つ de Bézout (2 つの整数uとvなど) も計算できます。 au + bv = PGCD( a , b ))。 aとb が互いに素である場合、 u はbを法とする a の乗算の逆数であり、これは特に便利なケースです。拡張Euclidアルゴリズムは、ディオファントス方程式ax+by = c に解があるかどうかを判断するための効率的な方法 (単純な Euclid アルゴリズムではすでに可能) だけでなく、この場合の特定の解を簡単に計算する方法も提供します。一般的な解決策を導き出します。
ユークリッドのアルゴリズムと同様に、拡張アルゴリズムは、可換体上の 1 つの変数を持つ多項式などのユークリッド環に一般化します。整数の場合と同様に、素数となる多項式を法とする多項式の逆数を計算できるため、多項式のリング上の商によって構築されるリングまたはボディの逆数の計算が可能になります (破断ボディ、完成ボディなど)。
導入例
たとえば、Euclid のアルゴリズムを使用した GCD 120 と 23 の計算を考えてみましょう。
| 120 ÷ 23 = 5 は 5 のままです |
| 23 ÷ 5 = 4 は 3 のままです |
| 5 ÷ 3 = 1 は 2 のままです |
| 3 ÷ 2 = 1 は 1 のままです |
| 2 ÷ 1 = 2 は 0 のままです |
この場合、最後から 2 番目の行で得られた剰余により、GCD は 1 になります。つまり、120 と 23 は互いに素です。ここで、前の分割を別の方法で表現してみましょう。
| 滞在する | = | 配当 | – | 商 | × | ディバイダー |
| 5 | = | 120 | – | 5 | × | 23 |
| 3 | = | 23 | – | 4 | × | 5 |
| 2 | = | 5 | – | 1 | × | 3 |
| 1 | = | 3 | – | 1 | × | 2 |
| 0 | = | 2 | – | 2 | × | 1 |
最初の 2 行に 120 と 23 が表示されていることを確認します。一方、各行 (表の2行目から) の右端の値は前の行の余りであり、被除数は3行目から始まる各同点で 2 行上に得られた余りになります。したがって、2 つの初期値 120 と 23 の線形結合として、連続する各剰余を段階的に計算できます。
ただし、この方法は最も効果的ではありません。より直接的なアルゴリズムを明らかにするために、最初にこれらの計算を作成します。
| r | = | あなた | × | もっている | + | v | × | b | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 120 | = | 1 | × | 120 | – | 0 | × | 23 | ||||||||||||
| 23 | = | 0 | × | 120 | + | 1 | × | 23 | ||||||||||||
| 5 | = | 120 | – | 5 | × | 23 | = | 1 | × | 120 | – | 5 | × | 23 | ||||||
| 3 | = | 23 | – | 4 | × | 5 | = | 1×23 | – | 4 | × | (1×120～5×23) | = | -4 | × | 120 | + | 21 | × | 23 |
| 2 | = | 5 | – | 1 | × | 3 | = | (1×120～5×23) | – | 1 | × | (-4×120 + 21×23) | = | 5 | × | 120 | – | 26 | × | 23 |
| 1 | = | 3 | – | 1 | × | 2 | = | (-4×120 + 21×23) | – | 1 | × | (5×120～26×23) | = | -9 | × | 120 | + | 47 | × | 23 |
最後の行では 1 = -9×120 + 47×23 が得られ、まさに必要なもの、 u = -9 およびv = 47 が得られることに注意してください。これは、1 が 1 であるため、-9 は 120 を 23 で法定して乗算する逆数であることを意味します。 = -9 × 120 (mod 23)。同様に、47 は 120 を法とする乗算の 23 の逆数です。
青色で示されているのは、前の 2 つの数値を除算した余りから gcd を求める連続計算です (通常の Euclid アルゴリズム)。対応する商は黄色で示されています。 2 つの緑色の列は、Bezout 係数 ( uおよびv ) をもたらす連続計算を示します。これらの係数は、黄色の列の商を使用して、同じ列の前にある 2 つの係数から計算されていることを確認できます。式は次の段落の表で指定されています。
