問題#Ⅰ015


問題#Ⅰ015 ★★☆☆

自然数nに対し、10n19=111111n(n で表す。たとえば、(1=1(2=11(3=111 である。

(1)m0以上の整数とする。(3m3mで割り切れるが、3m+1では割り切れないことを示せ。

(2)n27で割り切れることが、(n27で割り切れるための必要十分条件であることを示せ。


《ポイント》

(1)をどう使うかがポイントとなります。(1)自体は数学的帰納法で片付けてしまいましょう。


《解答例》

(1)

(3m3mで割り切れるが、3m+1では割り切れないことを数学的帰納法により示す。

m=0 のとき (0=1 であり、30=1 であるから成り立つ。

ここで、m=k のとき(3k3kで割り切れるが、3k+1では割り切れないと仮定する。このとき(3k+1=103k+119=(103k)319=103k19(1023k+103k+1)=(3k(1023k+103k+1)となる。101(mod9) より、1023k+103k+19で割った余りは 1+1+1=3 に等しいから、1023k+103k+13の倍数であるが9の倍数ではない。したがって仮定より (3k+13k+1で割り切れるが、3k+2では割り切れない。

以上より、0以上のすべての整数mに対して (3m3mで割り切れるが、3m+1では割り切れないことが示された。

 

(2)

knを正の整数とするとき、111111kn は 111111n の倍数であるから (33k33(=27) で割り切れる。

また、nに含まれる素因数3の個数をmとし、n=3mN(ただしN3と互いに素な正の整数)と置くと、(3n=103mN19=(103m)N19=103m19{(103m)N1++103m+1}=(3m{103m(N1)++103m+1}となる。(1)より、(3m3mで割り切れるが、3m+1では割り切れない。また、(★)103m(N1)++103m+1N個の項から成り、mod 3 を考えると()式はNに等しく、N3と互いに素な正の整数であることを考えると()式が3で割り切れることはない。

故に(3n3mで割り切れるが、3m+1では割り切れない。したがって、(3n27で割り切れるならばn27の倍数でなければならない。

以上より、n27で割り切れることが、(n27で割り切れるための必要十分条件であることが示された。


《コメント》

見慣れない記号が登場しますが、慌てずに何がどのように表現されているかを把握しましょう。(1)は一般的なnに関する命題なので数学的帰納法が有効だと発想できます。(2)は必要十分条件に関する問題です。このようなタイプの問題では必要性と十分性に分けて議論するのが一般的です。

因みに、本問で登場する(nという数は「レピュニット数」という名前が付いています。過去の投稿記事でレピュニット数を扱ったものがあるので興味がある方は是非ご覧下さい。

Number Theory の話題(Repunit Number と Zsigmondy’s Theorem)

(出典:東京大学 2008年)


戻る