ここから本文です

ユークリッドの互除法の活用について質問です。

chieroid_f8632fa9cb822da5428a555さん

2017/8/1007:36:48

ユークリッドの互除法の活用について質問です。

計算をさかのぼる所のやり方が全くわかりません。
8x+11y=1の解を求める問題のやり方を分かりやすく教えて下さい。

閲覧数:
181
回答数:
3

違反報告

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

hiruno_teiooさん

2017/8/1008:36:42

不定方程式は、特別解を1個見つければ、殆ど解けたようなもの。
そのための方法として、ユークリッドの互除法がある。
しかし、係数が大きくなると、互除法は意外と扱いにくいし手間がかかる。
以下の方法は、大抵の一次不定方程式に通用する。
特に係数が大きいときに有効。

8x+11y=1 ‥‥①。

小さいほうの係数に着目して、8(x+y)+3y=1、と変形する。
x+y=α ‥‥②とすると、8α+3y=1、となる。
これの特別解は、視察により簡単に、(α、y)=(-1、3)と分かる。
②より、x=α-y=-4

この時、①は、8(x+4)=11(3-y)、と変形できる。
11と8は互いに素から、kを整数として、
x+4=11k、3-y=8k、になる。



質問者:chieroid_f8632fa9cb822da5428a555さん。2017/8/1007:36:48

この質問は投票によってベストアンサーに選ばれました!

ベストアンサー以外の回答

1〜2件/2件中

並び替え:回答日時の
新しい順
|古い順

kurokannna10さん

2017/8/1007:47:47

8x+11y=1…①
8と11は互いに素なのでユークリッドの互除法を適用すると
11=8・1+3⇔3=11-8・1…②
8=3・2+2⇔2=8-3・2…③
3=2・1+1⇔1=3-2・1…④

④の右辺の2のところに③の右辺を代入
1=3-(8-3・2)・1
=3-8+3・2
=(1+2)・3-8
=3・3-8
②を代入
=(11-8・1)・3-8
=11・3-8・3-8
=11・3-8・(3+1)
=11・3-8・4
=8・(-4)+11・3

よって、8・(-4)+11・3=1より
x=-4、y=3が①を満たす解の一つである
①に代入すると
8・(-4)+11・3=1…⑤
①-⑤より
8(x+4)+11(y-3)=0
8(x+4)=-11(y-3)
8(x+4)=11(-y+3)…⑥
x,yが整数のとき、x+4,-y+3も整数
また、8と11は互いに素なので
等式⑥が成り立つためには
x+4=11k、-y+3=8k(kは整数)を満たせばよい
∴x=11k-4、y=-8k+3…(答)

mwpgadtさん

2017/8/1007:37:06

わかりませんね

あわせて知りたい

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

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

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

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

閉じる

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