Mathematics
Examination
Test
Archives
【4】 以下の文を読み,その中にある問1,問2,問3に答えよ.
つの自然数が互いに素であるとは,それらの最大公約数がとなることである.言いかえると,共通の約数で以上のものを持たない,ということである.
次の定理が成り立つ.
定理:をつの自然数であって,互いに素であるとする.このとき,整数をうまくとると,が成り立つようにできる.
例えばの場合,これらの最大公約数はなので,これらは互いに素である.とすると,
とできる.としても,
とできる.またの場合を見てみると,これらはやはり互いに素であり,とすれば,
とできる.さて,この定理を証明してみよう.
証明:この定理が主張しているのは,のある整数倍とのある整数倍との和がになるようにできる,ということである.そこで,の整数倍との整数倍との和として表される整数を全て集めた集合をとして,の中にがあるのか,という問題に置きかえてみよう.具体的には,は,とを整数として,という形の整数全体の集合であり,もしの中にが含まれているならば,はの整数倍との整数倍の和として表されるということになるので,定理が成り立つことになる.従って,この定理を証明するためには,の中にが含まれていることを証明すれはよい.
これを背理法で証明しよう.すなわち,の中にが含まれていないと仮定して,矛盾が生じるということを示すのである.
さて,なので,やの整数倍は必ずに含まれる.特に
とはに含まれている
ということに注意しよう.
に含まれる最も小さい自然数をとする.
「の中にははない」と仮定したのでである.はに含まれるので,の整数倍との整数倍の和として表されている.つまり,ある整数とがあって
となっている.
の整数倍となっている整数,すなわち,の倍数全体の集合をと表すことにしよう.具体的には,を整数としたとき,という形の整数の集まりがである.
と各戸わかりやすいかもしれない.次の命題が成り立つ.
命題:に含まれる整数は全てに含まれる.言いかえると,という形の整数は必ずの整数倍との整数倍の和として表される.
問1:この命題を証明せよ.
この命題から,集合は集合に含まれていることがわかったわけだが,その場合,次のつの場合のどちらかが成り立つ.
(1) である.すなわち,とは同じ集合である.
(2) の中には,に含まれない整数がある.
しかし,実は(1)のケースは成り立たない.なぜなら(1)が成り立つとすると,の中のどんな整数もの倍数になってしまい,とが互いに素であるという仮定に矛盾するからである.
問2:なぜ(1)が成り立つと,が互いに素であるという仮定に矛盾するのか説明せよ.
(1)は成り立たないので,(2)が成り立つ.すなわち,に含まれる整数で,の倍数でないものがあることになる.そのような整数のひとつをとしよう.もの整数倍ではないので,としてよい.すなわちは自然数であるとしてよい.はの倍数ではないので,をで割ったときの余りはではない.すなわち,をで割ったときの商を余りをとすると,でありとなっている.また,はという数で割ったときに出る余りなのでよりは真に小さい.すなわち
である.
はに含まれているので,の整数倍との整数倍の和として表されている.すなわち,ある整数とがあってとなっている.
であるので,にこれらを代入すると,すなわち,
が成り立っている.これは,がの整数倍との整数倍の和として表されることを示しており,はに含まれることになって矛盾が生じる.
問3:が成り立つとなぜ矛盾が生じるのかを説明せよ.
にが含まれないと仮定して矛盾が生じたので,はを含むことが証明された.すなわち,ある整数とがあってとなることが示された.