整数

ユークリッドの互除法の正当性については理解されているものとします。以下ではx,yを具体的に求めてみます。厳密な証明は他の回答者の回答等を参考にしてください。

a=329,b=218
とする。互除法でa,bの最大公約数を求める。

329=218(1)+111
218=111(1)+ 107
111=107(1)+ 4
107=4(26)+ 3
4=3(1)+ 1
3=1(3)+ 0

(a,b)=1

上のプロセスを逆にたどる。
1
=4-3
=4-(107-4(26))
=4(27)-107
=(111-107)(27)-107
=111(27)-107(28)
=111(27)-(218-111)(28)
=111(55)-218(28)
=(329-218)(55)-218(28)
=329(55)-218(83)
=329(55)+218(-83)

x=55,y=-83


上を見ればわかると思いますが補足すると、互除法の各ステップが
q0=q1(x0)+q2
q1=q2(x1)+q3
　　：
　　：
のようになっているので、例えばq3ならq3をq2とq1で表せるし、q2をq1とq0で表せるのでq3をq0とq1の整数倍の和で表わせるということです。

投稿日時 - 2009-09-15 03:12:07

つい先日。これと同一の質問に答えたばかり。
http://oshiete1.goo.ne.jp/qa5280904.html

投稿日時 - 2009-09-13 20:33:34