ユークリッドの互除法は最大公約数を計算する効率的な方法として古くから知られている方法です。 これについては，ユークリッドの互除法の項で説明しました。ここでは，その発展系の一つで色々なところでよく使われている，拡張ユークリッド互除法について説明します。

　ユークリッドの互除法は２つの自然数 x，y の最大公約数を効率的に計算する方法でした。

　例えば，GCD(13,5) を計算するのに，

13=2*5+3　　
5=1*3+2　　　
3=1*2+1
2=2*1　　　　　

を求めて，GCD(13,5)=1 とするものでした。今の場合この計算は，全く自明で，互除法は不要な感じがします。しかし，少し視点を変えるとそうとも言えません。上の式のうち最後の項を除いて，それぞれ，移項すると，

13-2*5=3
5-1*3=2
3-1*2=1

が得られます。ここで，３行目の式の2の所に，２行目の式を代入して，5と3に注目してくくると，

1=3-1*2=3-1*(5-1*3)=2*3-1*5

となります。この最後の項の3の所に１行目の式を代入して，さらに13と5に注目してくくると，

1=2*3-1*5=2*(13-2*5)-1*5=2*13-5*5

が得られます。即ち，

2*13-5*5=1

が得られます。この結果は例えば，13リットルの枡と5リットルの枡を使って1リットルを測ることが出来るとも解釈することが出来ます。

　同様なことを，12707,12319に対して適用してみると，

12707=1*12319+388　　
12319=31*388+291　　　
388=1*291+97
291=3*97　　　　　

より，

12707-1*12319=388
12319-31*388=291
388-1*291=97

が得られますが，これから，

97=388-1*291=388-1*(12319-31*388)=32*388-1*12319=32*(12707-1*12319)-1*12319
=32*12707-33*12319

が得られます。即ち，

32*12707-33*12319=97

が得られます。

　このことは一般に，成立して，次のように定式化できます。

x, yを0でない自然数とし，c=GCD(x,y)とする。このとき，

ax+by=c

となる整数a,bが存在する。そして，この a,b は実際に計算することが出来る。

　この定理の結果は，色々なところで使われる重要な結果です。その応用については以下で幾つか述べます。

　この定理の証明は，上の例のように，ユークリッドの互除法を逆に辿り，x,ｙを具体的に与えられれば，a,bを実際に計算できることを示すことで得られます。

　ここでは，このa,bを実際に計算するプログラムを書くことを考えて見ましょう。

• 一つの方法としては，上の計算例のように，互除法の過程をメモリに蓄えておき，その式を実際に逆に辿ることが考えられます。
  この場合，ある程度のメモリが必要になります。

• しかし，実はもう少し，巧妙な方法があります。

そのために，ユークリッドの互除法の証明の過程を振り返って見ましょう。

　便宜上 x=r₀，y=r₁と置きます。このとき，GCD(x,y)=r=r_nは次の式で与えられます。

(0)            r₀=q₁*r₁+r₂,        0< r₂ <r₁
(1)            r₁=q₂*r₂+r₃,        0< r₃ <r₂
(2)            r₂=q₃*r₃+r₄,        0< r₄ <r₃
                ...
(k-1)          r_k-1=q_k*r_k+r_k+1,        0< r_k+1 <r_k
                ...
(n-2)         r_n-2=q_n-1*r_n-1+r_n,    0< r_n <r_n-1
(n-1)         r_n-1=q_n*r_n

　このとき，i = 0, 1, 2, ..., k に対して，

(*1)                a_i * x + b_i * y = r_i　

と表されたとすると，

(*2)                a_k+1 = a_k-1 - q_k * a_k
                    b_k+1 = b_k-1 - q_k * b_k

に対して，

(*3)                a_k+1 * x + b_k+1 * y = r_k+1

が成立します。

　このことの証明をしましょう。実際，まず，(k-1) の式から，

r_k+1=r_k-1 - q_k*r_k

となりますが，この右辺に，(*1)のi=k-1 と，i=k の式を代入すると，

r_k+1=r_k-1 - q_k*r_k = (a_k-1 * x + b_k-1 * y) - q_k* (a_k * x + b_k * y )
=(a_k-1 - q_k* a_k )*x + (b_k-1 - q_k * b_k)*y

となります。この式に(*2)を代入すると，

r_k+1= a_k+1 * x + b_k+1 * y

が得られます。これが証明すべき式(*3)でした。

　そこで，a₀=1, b₀=0, a₁=0, b₁=1 と置 きます。このとき，x=r₀，y=r₁ と(0), (1) に注意すると，i=0,1 に対して，

a_i * x + b_i * y = r_i

が成立することが分かります。従って，(*1),(*2),(*3) の操作を，k=2, 3, ... n-1 まで続けると最終的に

a_n * x + b_n * y = r_n　

が得られます。ここで，r_nは=GCD(x,y)=c ですから，a = a_n , b = b_n と置くと,

a*x + b*y = c

が得られます。これが求める拡張ユークリッド互除法の結果でした。

　上の証明は，正整数 x, y に対して，

a*x + b*y = c

となる，a,b,c を求めるのに都合の良い形をしています。そこで，プログラムを書いてみましょう。

２つの入力値 x, y に対して，３つの出力値 a, b, c がありますから，Function ではなく Sub で実現します。

q_i，r_i  を計算するために，r_k-1=q_k*r_k+r_k+1 より，q_k = r_k-1 \  r_k, r_k+1 = r_k-1 mod  r_k, を利用します。また実際に使う変数は，r0, r1, r2, q1, a0, a1, a2, b0, b1, b2 のみで，適宜変数を置き換え添え字をずらすことにします。このようにすると，プログラムは上の証明の過程を，コード化することで直ちに得られます。

Sub ExGCD(x,y,a,b,c)
' Extended GCD
'  x>0 , y>0 に対して ax + by = c となる a, b, c=Gcd(a,b) を求める
'
r0 = x  : r1 = y
a0 = 1  : a1 = 0
b0 = 0  : b1 = 1
while (r1>0)
  q1 = r0 \ r1
  r2 = r0 mod r1
  a2 = a0 - q1*a1
  b2 = b0 - q1*b1
  r0 = r1 : r1 = r2
  a0 = a1 : a1 = a2
  b0 = b1 : b1 = b2
wend
c = r0
a = a0
b = b0
End Sub　

　拡張ユークリッドの互除法は，不定方程式の解を与えます。例として，不定方程式

1004*x+1001*y=1

を解きましょう。 ここで不定方程式とは上の等式を解として整数 (x,y) を考えるものです。またこれを解くとは上の等式を満たす整数(x, y) のすべての組を求めるものです。

　まず，拡張ユークリッドの互除法を用いて，一組の解，(334, -335)

1004*334 + 1001*(-335) = 1

が得られます。この式を元の方程式から引くと

1004*(x-334) + 1001*(y+335) = 0, 即ち，1004*(x-334) = -1001*(y+335)

が得られます。ここで，1004 と 1001 の最大公約数は 1 ですから，上式第２項は 1004 と 1001 の倍数，即ち，整数 k に対して

1004*(x-334) = -1001*(y+335) = 1004*1001*k

と表されます。従って，

x-334=1001*k, y+335=-1004*k

が得られます。これを整理すると，

x = 334 + 1001*k, y = -335 - 1004*k, ここで k は整数

が得られます。整数 k に対して上の (x,y) は元の等式を満たしますから，これがすべての解になります。

　拡張ユークリッドの互除法は，整数の合同における逆元を計算します。例として，合同式

12357 * x ≡ 102 mod 100102

を解いてみましょう。この合同式を解くとは，x を 12357 倍して，100102 で割ったときの余りが 102 となる整数 x をすべて求めることです。

12357 と 100102 に対して，拡張ユークリッドの互除法を適用すると，

30127*12357 - 3719*100102 = 1

が得られます。ここでこの式を100102 を法とした合同式としてみると，

30127 * 12357 ≡ 1 mod 100102

が得られます。従って，元の方程式の両辺に 30127 を掛けると

30127*(12357 * x) ≡ 30127*102 mod 100102

が得られます。ここで，30127 * 12357 ≡ 1 mod 100102　ですから，

x ≡ 30127 * 102 = 3072954 ≡ 69894 mod 100102

が得られます。即ち，x は 69894 + 100102*k の形の整数すべてであることが分かります。

　拡張ユークリッドの互除法はユークリッドの互除法の一寸した応用型ですが，強力な結果です。そしてその計算の複雑さはユークリッドの互除法の倍程度です。ここで，ユークリッドの互除法自身非常に高速に動作しますから，

拡張ユークリッドの互除法も高速に動作します！