東京大学 2016年 文系 第4問 解説

方針・初手

累乗の数をある整数で割った余りは、必ず周期性を持つことに着目する。

(1) および (2) では、合同式を用いて $3^n$ の 10 を法とする余り、および 4 を法とする余りの規則性を具体的に調べて周期を見つける。

(3) では、$x_{10} = 3^{x_9}$ を 10 で割った余りを求めるために、(1) の結果から「指数である $x_9$ を 4 で割った余り」が必要となることに気づくのがポイントである。同様に $x_9$ を 4 で割った余りを知るために、(2) の結果を用いる。

解法1

(1)

$3^n$ を 10 で割った余り $a_n$ を調べる。 法を 10 とする合同式を用いると、以下のようになる。

$$ 3^1 \equiv 3 \pmod{10} $$

$$ 3^2 \equiv 9 \pmod{10} $$

$$ 3^3 \equiv 27 \equiv 7 \pmod{10} $$

$$ 3^4 \equiv 81 \equiv 1 \pmod{10} $$

$$ 3^5 \equiv 243 \equiv 3 \pmod{10} $$

以降、余りは $3, 9, 7, 1$ の周期 4 で繰り返される。 問題文の指示により、(1) は結論のみでよいため、結果は最終的な答えにまとめる。

(2)

$3^n$ を 4 で割った余り $b_n$ を調べる。 法を 4 とする合同式を用いると、$3 \equiv -1 \pmod 4$ であるから、次が成り立つ。

$$ 3^n \equiv (-1)^n \pmod 4 $$

したがって、$n$ が奇数のとき余りは $-1 \equiv 3 \pmod 4$ となり、$n$ が偶数のとき余りは $1 \pmod 4$ となる。 ゆえに $b_n$ の値は $n$ の偶奇によって定まる。

(3)

数列 $\{x_n\}$ は $x_1 = 1$, $x_{n+1} = 3^{x_n}$ で定義されている。 求めるものは $x_{10}$ を 10 で割った余りである。

$x_{10} = 3^{x_9}$ であるから、これを 10 で割った余りを求めるには、(1) の結果より、指数である $x_9$ を 4 で割った余りが分かればよい。

まず、すべての正の整数 $n$ について、$x_n$ は奇数であることを数学的帰納法で示す。

(i)

$n=1$ のとき、$x_1 = 1$ であり奇数である。

(ii)

$n=k$ のとき、$x_k$ が奇数であると仮定する。 $x_{k+1} = 3^{x_k}$ であり、奇数である 3 の累乗は常に奇数であるから、$x_{k+1}$ も奇数である。

（i）, （ii） より、すべての正の整数 $n$ について $x_n$ は奇数である。

これより、特に $x_8$ は奇数である。 $x_9 = 3^{x_8}$ を 4 で割った余りは、(2) の結果において $n = x_8$（奇数）とした場合にあたるため、次が成り立つ。

$$ x_9 \equiv 3 \pmod 4 $$

したがって、$x_9$ は 0 以上の整数 $m$ を用いて $x_9 = 4m + 3$ と表すことができる。

これを用いて $x_{10}$ を 10 で割った余りを求める。 法を 10 とする合同式を用いると、

$$ x_{10} = 3^{x_9} = 3^{4m+3} = (3^4)^m \cdot 3^3 $$

(1) の計算より $3^4 \equiv 1 \pmod{10}$ であり、$3^3 = 27 \equiv 7 \pmod{10}$ であるから、

$$ x_{10} \equiv 1^m \cdot 7 \equiv 7 \pmod{10} $$

以上より、$x_{10}$ を 10 で割った余りは 7 である。

解説

累乗をある数で割った余りは必ず周期性を持つという、整数問題の基本事項を確認する問題である。

(3) で「$x_{10}$ を 10 で割った余りを知りたい」→「底が 3 だから、(1) より指数 $x_9$ を 4 で割った余りを知りたい」→「底が 3 だから、(2) より指数 $x_8$ の偶奇（2 で割った余り）を知りたい」というように、求めるべき条件が上位の指数へと連鎖していく構造（タワー型の累乗の余り）がこの問題の核心である。

誘導が非常に丁寧であるため、一つひとつ確実に処理していくことで完答を目指したい標準的な問題である。

答え

(1)

$$ a_n = \begin{cases} 3 & (n \text{ を 4 で割った余りが 1 のとき}) \\ 9 & (n \text{ を 4 で割った余りが 2 のとき}) \\ 7 & (n \text{ を 4 で割った余りが 3 のとき}) \\ 1 & (n \text{ を 4 で割り切れるとき}) \end{cases} $$

(2)

$$ b_n = \begin{cases} 3 & (n \text{ が奇数のとき}) \\ 1 & (n \text{ が偶数のとき}) \end{cases} $$

(3)

$$ 7 $$