整数について
a,bは整数とする (a,b)=1の時 ax+by=1を満たす整数x,yが存在することを示せ
で次のように証明してみました。
(1)(a,b)=dの時、ax+by=dを満たす整数x,yが存在するという定理を用 いて考えてみる。
(a,b)=dだからユークリッドの互助法を使ってゆくと最後はdで割り 切れる。計算が次のようになったとする。
a=bq_1+r_1 従ってr_1=a-bq_1・・・(1)
b=r_1q_2+r_2 従ってr_2=b-r_1q_2・・・(2)
r_1=r_2q_3+r_3 従ってr_3=r1-r_2q_3・・・(3)
r_2=r_3q_4+0 (r_3=d)
ここで(3)に(2)を代入
d=r_3=r_1-(b-r_1q_2)q_3
=r_1-bq_3+r_1q_2q_3
=r_1(1+q_2q_3)-bq_3・・・(4)
(4)のr_1へ(1)を代入
d=(a-bq_1)(1+q_2q_3)-bq_3
=a+aq_2q_3-bq_1-bq_1q_2q_3-bq_3
=a(1+q_2q_3)+(-q_1-q_1q_2q_3-q_3)b
(1+q_2q_3)=x , (-q_1-q_1q_2q_3-q_3)=yとおくと
d=xa+by 従って(a,b)=ax+by
よって(a,b)=1の時にax+by=1となる整数x,yが存在する。
このように証明しました。大丈夫でしょうか？
(2)また、次の定理を使った場合はどう証明しますか。
定理・・自然数a,b(a>b)についてaをbで割りその整商をq、余りをr とするとa=bq+r (0≦r<b) このとき(a,b)=(b,r)
この定理を使った場合の証明はなりますか。 よろしくお願いしま す。
