Question

グダグダ

数学　チャートA 例題121

(1)についてです。
回答を読んだのですが、何から手をつけて良いのかがさっぱり分かりません。解説には[ユーグリットの互助法を用いる]と記載されていますが、どのように利用するのですか？

ご解説宜しくお願いしますm(_ _)m

Answer 1

✨ คำตอบที่ดีที่สุด ✨

としさん

11x + 19y = 1

最終的には 11*〇 + 19*△ = 1 となる　(〇、△)を１個求めるのが目的です。 ※ 特殊解と言います。
ユークリッドの互除法は、その手段の１つです。

11,19だけに着目していきます。ユークリッドの互除法で最大公約数を求めるのと同じです。

19 = 11*1 + 8　※ 11,19の大きい方を小さい方で割ります。商１、余り8となります。
11 = 8*1 + 3 ※ 先ほどの11を余り8で割ります。 商１、余り3となります。
8 = 3*2 + 2
3 = 2*1 + 1 ※ 余りが1となるまで繰り返します。

これを逆算していきます。
それぞれ、式を加工します。
　19 = 11*1 + 8　⇒ 8 = 19 - 11*1
　11 = 8*1 + 3　⇒ 3 = 11 - 8*1
　8 = 3*2 + 2　⇒ 2 = 8 - 3*2
　3 = 2*1 + 1　⇒ 1 = 3 - 2*1

1 = 3 - 2*1 の "2" に "2 = 8 - 3*2" を代入します。
　1 = 3 - (8 - 3*2)*1 = 3*1 - 8*1 + 3*2*1 = 3*(1 + 2*1) - 8*1 = 3*3 - 8*1
これに "3 = 11 - 8*1"を代入します。
　1 = (11 - 8*1)*3 - 8*1 = 11*3 - 8*1*3 - 8*1 = 11*3 - 8*(1*3 + 1) = 11*3 - 8*4
さらに "8 = 19 - 11*1"を代入します。
　1 = 11*3 - (19 - 11*1)*4 = 11*3 - 19*4 + 11*1*4 = 11*(3 + 1*4) - 19*4 = 11*7 - 19*4

よって 11*7 + 19*(-4) = 1 となり 特殊解 (7,-4)を見つけることができました。となります。

　

グダグダ

有難う御座います😄
返信が遅れてしまいすみませんでした