問題5-4
2つの整数αとの最小公倍数をとする。 このとき との任意
の公倍数ではの倍数であることを証明せよ。
方針
Folk c=44th
とされるのが
cを1で割った商を余りをとすると
=ltr≦r< 1)←割る数)×(商)+(余り)
が成り立ちます。 0が証明できれば, cは1で割り切れるのでは
の倍数となります。
そこで,r=0と仮定します (背理法)。 このとき、
との最小公倍数なので、はαの倍数 (ア) かつの倍数
(イ)です。
また,caとりの公倍数なので,cは4の倍数(ウ) かつはもの
倍数 (エ)です。
アウより、とはαで割り切れるので、
r=c-lg
もαで割り切れます。 よってはαの倍数です。
同様に,,エよりはの倍数です。
これによりはaとbの公倍数(両方に共通の倍数)となり矛盾です。
なぜ, 矛盾かわかりますか (解答のポイント 参照)? じっくり考
えてみてください。
問題 5.
