陥没地帯 (247) - ノリの悪い日記

$2008$ 年東大理科の問題. この問題は、直前の記事 $(246)$ に出てきた, $1$ が並ぶ数字, つまりレプユニット数に関する問題である. (素数であるレプユニット数は, 現在まで $10$ 個以下しか見つかっていないにもかかわらず, 無限にあると予想されており, これは未解決問題である.) もっとも前回の問の本質は, レプユニット数というよりは, 連続する素数の積でもあるシエラザード数 $1001 = 7 \times 11 \times 13$ *1がもつ性質 ( $123\times 1001 = 123123$ ) の発展形という趣きがある. 「シエラザード数」の命名はもちろん, 「千夜一夜物語」からきている. $1000$ と $1$ を対比させた文学の他の例として, 「伊勢物語」の次の歌がある.

秋の夜の千夜を一夜になせりとも
ことば残りてとりや鳴きなむ

【問】
自然数 $n$ に対し,

$\displaystyle{\frac{10^n - 1}{9} = \overbrace{111\cdots111}^{n\text{個}}}$

を $\displaystyle{ \boxed{n}}$ で表す. たとえば $\displaystyle{ \boxed{1} = 1}$ , $\displaystyle{ \boxed{2} = 11}$ , $\displaystyle{ \boxed{3} = 111}$ である.

$(1)$ $m$ を $0$ 以上の整数とする. $\boxed{3^m}$ は $3^m$ で割り切れるが, $3^{m+1}$ では割り切れないことを示せ.

$(2)$ $n$ が $27$ で割り切れることが, $\boxed{n}$ が $27$ で割り切れるための必要十分条件であることを示せ.

【解】
$(1)$
問題の主張を数学的帰納法で証明すればよい.

$m = 0$ とき, $\boxed{3^0} =1 = 1\times 3^0$ だが, $1$ は $3^1 =3$ では割り切れないので成立する.

$\displaystyle{ \boxed{3^{m+1}} \\= \frac{10^{3^{m+1}} -1}{9} \\= \frac{(10^{3^{m}})^3-1}{9} \\= \frac{10^{3^{m}}-1}{9} \{(10^{3^{m}})^2 + 10^{3^{m}}+1\} }$

したがって,

$\displaystyle{ \boxed{3^{m+1}} = \boxed{3^m} \{(10^{3^{m}})^2 + 10^{3^{m}}+1\} }$

だが, $(10^{3^{m}})^2 + 10^{3^{m}}+1$ は, $3$ で割り切れ, $9=3^2$ では割り切れないので, $\boxed{3^m}$ に帰納法の仮定を使うと $\boxed{3^{m+1}}$ は, $3^{m+1}$ で割り切れ, $3^{m+2}$ では割り切れない.

$(2)$
必要条件であること:

$\boxed{n}$ は $27$ で割り切れるので, $3$ でも割り切れるから, $\boxed{n}$ の $1$ の個数 $n$ は $3$ で割り切れる. したがって,

$\displaystyle{ k = \frac{n}{3}}$

とおくと,

$\boxed{n} \\= 111 \times 1000^ {k-1}+ \cdots + 111 \times 1000 + 111$

のように書ける.

$1000=999+1 \equiv 1$ ( $\mathrm{mod}\ 27$ )

から,

$\boxed{n} \equiv 111k = 37n$ ( $\mathrm{mod}\ 27$ )

つまり,

$37n \equiv 0$ ( $\mathrm{mod}\ 27$ )

であるが, $27$ と $37$ は互いに素であるので,

$n \equiv 0$ ( $\mathrm{mod}\ 27$ )

であり, $n$ は $27$ で割り切れる.

十分条件であること:

$n$ は $3$ でも割り切れるので, 先程とまったく同じ議論をすれば,

$\boxed{n} \equiv 37n$ ( $\mathrm{mod}\ 27$ )

となるが, $n$ は $27$ で割り切れるのだから,

$\boxed{n} \equiv 0$ ( $\mathrm{mod}\ 27)$

である.
//

*1: $10^3 = 1001-1$ だから $7$ , $11$ , $13$ の倍数判定法は同じ方法が使えることがわかる. つまり, 調べたい数字を下から $3$ 桁ずつ区切り, 下から奇数番目のグループと偶数番目のグループの和をそれぞれ計算し, 両者の差が $7$ , $11$ , $13$ の倍数であるかどうかをそれぞれ調べればよい. 例: $123450789$ の場合, 奇数番目の和は $123+789=912$ , 偶数番目は $450$ で差は, $462$ . $2\times 4 + 62 = 70$ なので $7$ の倍数, $4-6+2 =0$ なので $11$ の倍数, $462 / 77 < 10$ なので $13$ の倍数ではない. $13$ の倍数は, $4\times(-3)^2 +6\times (-3) +2$ を計算してもよい.