問題#Ⅰ015 ★★☆☆
自然数に対し、 を で表す。たとえば、、、 である。
(1)を以上の整数とする。 はで割り切れるが、では割り切れないことを示せ。
(2)がで割り切れることが、 がで割り切れるための必要十分条件であることを示せ。
《ポイント》
(1)をどう使うかがポイントとなります。(1)自体は数学的帰納法で片付けてしまいましょう。
《解答例》
(1)
はで割り切れるが、では割り切れないことを数学的帰納法により示す。
のとき であり、 であるから成り立つ。
ここで、 のとき はで割り切れるが、では割り切れないと仮定する。このときとなる。 より、 をで割った余りは に等しいから、 はの倍数であるがの倍数ではない。したがって仮定より はで割り切れるが、では割り切れない。
以上より、以上のすべての整数に対して はで割り切れるが、では割り切れないことが示された。
□
(2)
、を正の整数とするとき、 は の倍数であるから は で割り切れる。
また、に含まれる素因数の個数をとし、(ただしはと互いに素な正の整数)と置くと、となる。(1)より、 はで割り切れるが、では割り切れない。また、は個の項から成り、 を考えると式はに等しく、がと互いに素な正の整数であることを考えると式がで割り切れることはない。
故にはで割り切れるが、では割り切れない。したがって、がで割り切れるならばはの倍数でなければならない。
以上より、がで割り切れることが、 がで割り切れるための必要十分条件であることが示された。
□
《コメント》
見慣れない記号が登場しますが、慌てずに何がどのように表現されているかを把握しましょう。(1)は一般的なに関する命題なので数学的帰納法が有効だと発想できます。(2)は必要十分条件に関する問題です。このようなタイプの問題では必要性と十分性に分けて議論するのが一般的です。
因みに、本問で登場するという数は「レピュニット数」という名前が付いています。過去の投稿記事でレピュニット数を扱ったものがあるので興味がある方は是非ご覧下さい。
Number Theory の話題(Repunit Number と Zsigmondy’s Theorem)
(出典:東京大学 2008年)
戻る