Question

チナミ

解説がなくて、わかるひとお願いします！

図 () 整数4を正の整数で割った余りをヵ, をで割った余りをとする。gと1の
最大公約数は, ァ」 と ヵ。 の最大公約数と一致することを証明せよ。

Answer 1

✨ ベストアンサー ✨

ピタゴラス

問題より
a=b*q+r_1 、b=r_1*q'+r_2 (q ,q' は整数)

以下自然数 x、yの最大公約数をG(x , y)と表記する。

G(a, b)=g としたら、明らかに r_1 はgの倍数。

ここで、G(b, r_1)=g' (g'>g) と仮定したら
aはg'の倍数となり、G(a, b)=gである事に反する。
よって、G(b, r_1)=g

以上より
G(a, b)=G(b, r_1) ･･･①
上と同様にして
G(b, r_1)=G(r_1, r_2) ･･･②

①、②より
G(a, b)=G(r_1, r_2) となり題意を満たした。

ユークリッドの互除法の証明ですね。
分からなければ言ってください。😀

チナミ

回答ありがとうございます。r1がgの倍数というのはどういうことでしょうか？

ピタゴラス

今、aとbの最大公約数をgとしましたのでa、bは共にgの倍数という事が分かります。

これより、a=a'*g、b=b'*g (a'とb'は互いに素)
と置けます。
よって、
a=b*q+r_1 ⇔ (a'*g) = (b'*g)*q+r_1 (代入)
⇔ (a'-b'*q)*g = r_1 (移行してgでくくる)
⇔ r_1=C*g (C=a'-b'*q : 整数)
∴ r_1はgの倍数。

こんな感じでどうでしょうか？
このように、しっかり書くとだいぶ長くなるので先の証明では省略してしまいました。(すみません🙇)
もし、分からなくても一旦ノートに書いてみると、恐らく理解出来るはずです。😀

チナミ

理解できました！ありがとうございます😊