整数

質問

ユークリッドの互除法とa=bq+rを使って次の証明をお願いします。
「a,bは整数とする。(a,b）=1のときax+by=1を満たす整数x,yが存在することを示せ」
(a,b)=1というのは互いに素つまり１以外に公約数を持たないということです。
非常に困っています　よろしくお願いします。

回答No.2

noname#102340

ユークリッドの互除法の正当性については理解されているものとします。以下では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の整数倍の和で表わせるということです。

お礼

ありがとうございます。

回答No.1

arrysthmia

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