Question

ゆめこ

272(6)を教えていただきたいです。
解説では互除法の計算が25=11×2+3で終わっているのですが、なぜ11=3×3+2のように互除法を続けないのでしょうか。解説していただきたいです。

5 6n+9 と 5n+8が互いに素になるような100以下の自然数nは全部
最大公約数はbとrの最大公約数に等しい。
等式 aー ba+ァを満たす自然数 a, b, q. rについて, aとbの
24 ユークリッドの互除法
2つの自然数A, Bの最大公約数を(A, B)で表す
をすべて求めよ。 ただし、 次のことを用いてよい。
よって、4n+9と 3n+8の最大公約数は n+1 と5の最大公約数に等しい。
163
4n+9-(3n+8)·1+n+1,
3n+8-(n+1)·3+5
ゆえに、カ+1は5の倍数である。
また。25n+1S51 であるから
n+1=5, 10, 15, 20, 25, 30, 35, 40, 45, 50
カ=4. 9, 14, 19, 24, 29, 34, 39, 44, 49 「器
したがって
(4n+9, 3n+8)=(3n+8, n+1)=(n+1, 5)
*(2) 833, 646
(1) 961, 217
(3) 498, 223
*(4) 731, 301
(5) 957, 754
(6) 1273, 469
99 次の等式を満たす整数x, yの組を1つ求めよ。
(2) 63x+44y==2
H(5) 141x-52y=4
(1) 24x+19y=1
*(4) 95x+28y=1
(3 86x-49y=3
(6 25x-61y=9
A CLear)
273 4984 と 3471の最大公約数を, 互除法を用いて求めよ。
B
74/4n+15 と 3n+13 の最大公約数が7になるような50以下の自然数nを
べて求めよ。
Ole
B CLear
個あるか。

互除法

Answer 1

✨ Jawaban Terbaik ✨

HIROBA〜

イコール9なので
9の約数の3が出せれば
解決できるからですね

一般的には
イコール1になるまで繰り返して
結果を9倍することにはなります
今回は特別なケースです

ゆめこ

ご解説ありがとうございます。
もしイコール１になるまで互除法を続け、最後にかける９をしてしまったら、答えは間違ってしまいますか？

HIROBA〜

やってみていませんが
同じになるでしょうね
だからこそ
そこまでやる必要がないと考えられるのです

HIROBA〜

補足しておきます
１枚目が1まで求めてから出た答えで
２枚目左が3から求めた答えです

一見すると違う答えのように見えますが
１枚目の答えは数がそうとう大きいので
２枚目の右のようにして数を小さくして行くと
最終的には２枚目左の式になります
つまりどちらも同じ答えになるのですが
１枚目の答えは数を小さくしていく手続きがプラスされるので
２枚目のやり方の方が優れていると言えます

ゆめこ

わざわざ式を書いて下さりありがとうございます。とても納得できました。