ここから本文です

定理2の証明お願いします

yga********さん

2019/9/914:39:28

定理2の証明お願いします

定理,I1,K-1,証明,Bézout's lemma,ベズー,gcd

閲覧数:
20
回答数:
1

違反報告

ベストアンサーに選ばれた回答

arg********さん

2019/9/1100:45:33

ベズーの補題(Bézout's lemma)という名前が付いています。検索するときに参考になれば。
証明
(<=)

a*x+b*y = 1 (1)
が成立していると仮定する.
d = gcd (a, b), a' = a / d, b' = b / d とおけば,
a*x + b*y = d * (a'*x + b'*x) となり, (1)式の左辺は d の倍数になる。
そこで, d != 1 と仮定すると,
(ここで a != b は a と b が等しくないことを表す)
|a*x+b*y| = d*|a'*x + b'*x| >= d != 1
即ち a*x+b*y != 1 となって (1) に矛盾.
したがって d = 1, 即ち a と b は互いに素である.
(=>)
除算アルゴリズムを a, b に逐次適用してゆくと,
a = b * q_1 + r_1, (1 <= r_1 < b)
b = r_1 * q_2 + r_2, (1 <= r_2 < b)
r_1 = r_2 * q_3 + r_3, (1 <= r_3 < b)
...
r_(k-2) = r_(k-1) * q_k + r_k, (1 <= r_k < r_(k-1))
r_(k-1) = r_k * q_(k+1) + r_(k+1), (r_(k+1) = 0)
となるような q_i, r_i が存在する. ここで r_k = gcd (a, b)となることに注意.
これをユークリッドの互除法(Euclidean algorithm)という.
このとき,
r_1 = a - b* q_1,
r_2 = -a * q_2 + b * (1 + q_1 * q_2)
...
となり, 一般には r_i = a*x_i + b*y_i と書ける.
(r_(i+1) = r_(i-1) - r_i * q_(i+1) から帰納法で証明できる.)
このとき, 漸化式
x_(i+1) = x_(i-1) - q_(i+1) * x_i
y_(i+1) = y_(i-1) - q_(i+1) * y_i
が成り立ち, 最終的に gcd (a, b) = r_k = a*x_k + b*y_k が得られる.
今 gcd (a, b) = 1 であるから,
a*x_k + b*y_k = 1
となる. 即ち a*x + b*y = 1 となるような整数の組 (x, y) (=(x_k, y_k)) が存在する. ■

質問した人からのコメント

2019/9/12 18:28:37

ありがとうございます。逆は理解しました。残りも頑張ります。

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる