ユークリッド互除法なんですが最高公倍数が15なのは分かるんですけどrとsの解き方が分かりません。 教

ユークリッド互除法なんですが最高公倍数が15なのは分かるんですけどrとsの解き方が分かりません。
教えてください！

No.4 回答者： ありものがたり 回答日時： 2023/02/27 14:48

ユークリッドの互除法を使って一次不定方程式を解く手順は、

多くの本やサイトで解説されています。
「拡張互除法」と呼ばれていることが少なくないので、
こちらの名前で検索すると見つけやすいかもしれません。
「拡張」と呼ばれるのは、たぶん、どこかのコンピュータの
ライブラリの関数名の名残りです。
数学的には、拡張でもなんでもない、ユークリッドの互除法
そのものなんですけどね。

この手法にピンと来ない人があるのは、
「余りを他の式へ代入する」という説明に抵抗があるから
ではないかと思います。変数ではなくて
定数に何かを代入するとは何事か？って話です。
例えば 15=255-60×4 と 60=315-255×1 とから
15=255-(315-255×1)×4 という式を作ることを言ってるのですが、
「定数へ代入する」ことに違和感があるなら、
15=255-60×4 式中の 60 を 315-255×1 で置き換える
とでも言い換えておけばよいのではないでしょうか。

No.3 回答者： kairou 回答日時： 2023/02/27 14:12

255 と 315 の約数では、先ず 両方共 5 の倍数であることは分かりますね。

で、それぞれを 5 で割って 57 と 63 になります。
これも 見ただけで 3 の倍数であることが分かります。
3 で割ると 17 と 63 になります。
17 は素数ですから これ以上の約数は ありません。
従って 255 と 315 の最大公約数は 5x3=15 で 15になります。
但し r と s を求める計算には 適していませんが。

ユークリッドの互除法を使えば、
（掛けるの記号を * で表します。）
315=255*1+60 →　60=315-255*1 ・・・①
255=60*4+15 →　15=255-60*4 ・・・②
60=15*4+0 。
（余りが 0 になったことで 最大公約数が 15 であることが分かる）
② に ① を代入する。
15=255-(315-255)*4=255*5-315*4=255*5+315*(-4) 。
つまり 15=255*5+315*(-4) 。
最大公約数=255r+315s から、最大公約数 15, r=5, s=-4 。

No.2 回答者： ご意見をお願いします。 回答日時： 2023/02/27 03:42

255と315の最大公約数を求めてみます。

315÷255＝1あまり60…①
255÷60＝4あまり15…②
60÷15＝4あまり0…③
よって最大公約数は15

ここで、①～③の式のあまりに注目して各式を変形してみます。

①より､､､
60＝315-255×1…④
②より､､､
15＝255-60×4…⑤
⑤に④を代入して､､､
15＝255-(315-255×1)×4
＝255-(315-255)×4
＝255-315×4+255×4
＝255×5-315×4
＝255×5+315×(-4)
つまり、
15＝255×5+315×(-4)
よって、
15＝255r+315×sを満たす(r,s)＝(5,-4)

同様に288と639の最大公約数を求めてみます。
639÷288＝2あまり63…①
288÷63＝4あまり36…②
63÷36＝1あまり27…③
36÷27＝1あまり9…④
27÷9＝3あまり0…⑤
よって最大公約数は9
①より､､､
63＝639-288×2…⑥
②より､､､
36＝288-63×4…⑦
③より､､、
27＝63-36×1…⑧
④より､､、
9＝36-27×1…⑨
ここから先は大変ですが､､、
⑨に⑧を代入して整理し、それに⑦を、さらに⑥を代入すれば、rとsが求まるはずです。

No.1 回答者： Tacosan 回答日時： 2023/02/27 01:24

「最高公倍数」とやらがなんなのかわからんがユークリッドの互除法でも使ってみる?