東京大学 文系 2016年度 第4問 解説
問題編
【問題】
以下の問いに答えよ。ただし、(1)については、結論のみを書けばよい。
(1) nを正の整数とし、$3^n$を10で割った余りを$a_n$とする。$a_n$を求めよ。
(2) nを正の整数とし、$3^n$を4で割った余りを$b_n$とする。$b_n$を求めよ。
(3) 数列$\{x_n\}$を次のように定める。\[x_1=1、x_{n+1}=3^{x_n} \quad (n=1,2,3,\cdots)\]$x_{10}$を10で割った余りを求めよ。
【考え方】
(1)は書き出せばすぐに法則に気づきます。(2)も書き出せばすぐに答えはわかるでしょう。それを示すのに少しテクニックは要りますが、整数問題ではよく使う手法であり、難しくはありません。
(3)は(1)と(2)をよく見ればすぐにひらめくでしょう。見た目ほど怖くはなく、むしろサービス問題です。
解答編
【問題】
以下の問いに答えよ。ただし、(1)については、結論のみを書けばよい。
(1) nを正の整数とし、$3^n$を10で割った余りを$a_n$とする。$a_n$を求めよ。
(2) nを正の整数とし、$3^n$を4で割った余りを$b_n$とする。$b_n$を求めよ。
(3) 数列$\{x_n\}$を次のように定める。\[x_1=1、x_{n+1}=3^{x_n} \quad (n=1,2,3,\cdots)\]$x_{10}$を10で割った余りを求めよ。
【解答】
(1)
$\mathrm{ mod } \ 10$とする。
$3^1\equiv 3$、$3^2\equiv 9$、$3^3\equiv 7$、$3^4\equiv 1$なので、$a_n$は次のようになる（mは正の整数）。
\begin{eqnarray}
a_n
=
\begin{cases}
3 & ( n=4m-3 ) \\
9 & ( n=4m-2 ) \\
7 & ( n=4m-1 ) \\
1 & ( n=4m )
\end{cases}
\end{eqnarray}
(2)
$3^n=(4-1)^n$なので、$3^n\equiv (-1)^n \pmod 4$である。よって、$b_n$は次のようになる（mは正の整数）。
\begin{eqnarray}
b_n
=
\begin{cases}
3 & ( n=2m-1 ) \\
1 & ( n=2m )
\end{cases}
\end{eqnarray}
(3)
$x_{n+1}=3^{x_n}$なので、$x_n$は奇数。よって、(2)から、$n\geqq 2$のとき、$x_n$を4で割った余りは3となる。このことと(1)より、$n\geqq 3$のとき、$x_n$を10で割った余りは7となる。よって、$x_{10}$を10で割った余りは、7。
【解答終】
【解説】
誘導も丁寧で、特に難しいところもありません。しいて言うなら、(2)ですか。(2)は、$3^2\equiv 1 \pmod 4$というのを使って解いてもいいと思います。整数問題にしては易しい問題です。
