Question

みさ

ユークリッドの互除法で
a=bq+rの
『aとbの最大公約数』と『bとrの最大公約数』が等しくなるのがよく分かりません…。
なんで最大公約数なんですか？
『aとbの公約数』と『bとrの公約数』は全部同じなんですか？
よろしくお願いします🙇⤵

ユークリッドの互除法

Answer 1

✨ ベストアンサー ✨

とこきち

aとbの最大公約数をpとすると
a=pk,b=pl（kとlは互いに素）とおける。
この時、r=a-bq=pk-pql=p(k-ql)
kとlは互いに素だからlとk-qlも互いに素
よってbとrも最大公約数にpを持つことがわかる。
ただし、a=bqで表される場合はr=0となるのでうまく行かないですね。
ただの公約数についても同じようにしてやれば証明できますよ。先の場合と同様にうまくいく場合とそうでない場合がありますが、、、。

みさ

ありがとうございます🙇🙇