ユークリッド互除法については下記参照 http://blog.goo.ne.jp/kaizo01/e/4c9311a2939c9bfdf686c666757620a8
ユークリッド互除法をa,b≧0に適用したときの剰余数列を
r_0=a,r_1=b,r_2,r_3,・・・・・・,r_(n+1)
商数列を q_1,q_2,q_3,・・・・・・q_n とする
今
x=(-1)^n・x_n y=(-1)^(n+1)・y_n
が次のような性質を満足するように数列(x_k),(y_k)(0≦k≦n+1)を構成する
x_0=1, x_1=0, y_0=0, y_1=1,
x_(k+1)=q_k・x_k+x_(k+1)
y_(k+1)=q_k・y_k+y_(k+1)
すると、0≦k≦n+1に対して r_k=(-1)^k・x_k・a+(-1)^(k+1)・y_k・b が成り立つ
（証明）
k≧2についての数学的帰納法による
r_0=(-1)^0・x_0・a+(-1)^1・y_0・b=1・1・a+(-1)・0・b=a
r_1=(-1)^1・x_1・a+(-1)^2・y_1・b=-1・0・a+1・1・b=b
k-2,k-1に対して定理が成り立つとすると
r_(k-2)=q_(k-1)・r_(k-1)+r_k r_k=q_(k-1)・r_(k-1)-r_(k-2)
=q_(k-1)((-1)^(k-1)・x_(k-1)・a+(-1)^k・y_(k-1)・b)-((-1)^(k-2)・x_(k-2)・a+(-1)^(k-1)・y_(k-2)・b)
=(-1)^k・a（x_(k-2)+q_(k-1)・x_(k-1))+(-1)^(k+1)・b（y_(k-2)+q_(k-1)・y_(k-1))
=(-1)^k・x_k・a+(-1)^(k+1)・y_k・b
よってkのとき成り立つ
（証明終わり）
以下計算例を示す
128と80の最大公約数gcd(128,80)=128x+80yと整数x、yを求める
ユークリッド互除法によりr_kを計算する
ここでa mod bはaをbで割った余りを表す
gcd(128,80)=gcd(r_0,r_1)=gcd(80,128 mod 80)
=gcd(80,48)=gcd(r_1,r_2)=gcd(48,80 mod 48)
=gcd(48,32)=gcd(r_2,r_3)=gcd(32,48 mod 32)
=gcd(32,16)=gcd(r_3,r_4)=gcd(16,32 mod 16)
=gcd(16,0)=r_4=16
よってn=4
またq_1=1,q_2=1,q_3=1,q_4=2
x_0=1,x_1=0 y_0=0,y_1=1
x_2=q_1・x_1+x_0=1・0+1=1
y_2=q_1・y_1+y_0=1・1+0=1
x_3=q_2・x_2+x_1=1・1+0=1
y_3=q_2・y_2+y_1=1・1+1=2
x_4=q_3・x_3+x_2=1・1+1=2
y_4=q_3・y_3+y_2=1・2+1=3
r_4=(-1)^4・x_4・128+(-1)^5・y_4・80
=2・128-3・80
=256-240=16
よって
x=2, y=-3
