最大公約数

質問

★a,bを自然数とする。a,bをa,bの最大公約数で割って得た商をそれぞれa',b'とするとき、それぞれa',とb'は互いに素であることを証明せよ。

という問題はどういう解法になるでしょうか？

素でないとしたら→a',b'がk*a'',k*b''と書けると思うんですが、素である場合はどう示せばよろしいでしょうか？

回答No.1

sanori · ベストアンサー

こんばんは。

さて、
最大公約数をｍと置くと、
ａ　＝　ａ’ｍ
ｂ　＝　ｂ’ｍ

（ここから背理法）
ここで、ａ’とｂ’が互いに素でないとすれば、
ａ’とｂ’の公約数が存在する。
その公約数をｎと置き
ａ’、ｂ’をｎで除した商をａ”、ｂ”と置くと、
ａ’＝　ａ”ｎ
ｂ’＝　ｂ”ｎ
これを元の式に代入すると、
ａ　＝　ａ”ｍｎ
ｂ　＝　ｂ”ｍｎ
となるが、
ここで、ｎはａとｂの約数であるから、ｍはａとｂの最大公約数ではない。
これは、「ａ’とｂ’が互いに素でない」つまり「ａ’とｂ’の公約数が存在する」と矛盾する。

以上、ご参考に。

お礼

素晴らしい回答ありがとうございます！！背理法ですね！！思い出しました！！素早い回答ありがとうございました★☆