問題#Ⅰ003 ★★☆☆
以下の問いに答えよ。ただし、（１）については、結論のみを書けばよい。
（１）$n$を正の整数とし、$3^n$を$10$で割った余りを$a_n$とする。$a_n$を求めよ。
（２）$n$を正の整数とし、$3^n$を$4$で割った余りを$b_n$とする。$b_n$を求めよ。
（３）数列$\{x_n\}$を次のように定める。
$x_1=1$、$x_{n+1}=3^{x_n} \ (n=1,2,3,\cdots)$
$x_{10}$を$10$で割った余りを求めよ。
《ポイント》
本問も実は下一桁の問題です。（１）や（２）で剰余の周期に関するヒントを与えてくれています。誘導が丁寧なので完答を目指しましょう。
《解答例》
（１）（問題文では要求されていませんが、考え方も示しておきます）
$3^1=3$、$3^2=9$、$3^3=27$、$3^4=81$、$3^5=243$、$\cdots$ となるから$a_n$は周期$4$で$3,9,7,1$を循環する。したがって$m$を$0$以上の整数として、$a_{4m+1}=3$、$a_{4m+2}=9$、$a_{4m+3}=7$、$a_{4m+4}=1$ となる。
（答）$\color{red}{\begin{cases} a_{4m+1}=3 \\ a_{4m+2}=9 \\ a_{4m+3}=7 \\ a_{4m+4}=1 \\ \end{cases} \ (m \in \mathbb{Z} \geqq 0 )}$
（２）
$3^n \equiv (-1)^n \pmod{4}$ より、$n$が奇数のとき $3^n \equiv -1 \equiv 3 \pmod{4}$、$n$が偶数のとき $3^n \equiv 1 \pmod{4}$ となるから、$n$が奇数のとき $b_n=3$、$n$が偶数のとき $b_n=1$ である。
（答）$\color{red}{\begin{cases} a_{2m+1}=3 \\ a_{2m+2}=1 \end{cases} \ (m \in \mathbb{Z} \geqq 0 )}$
（３）
漸化式より、$x_n$は任意の正の整数$n$に対して奇数であり、$x_n$は$3$の冪であるから（２）の結果より、$x_n$を$4$で割った余りは $n \geqq 2$ で$3$となる。さらに（１）の結果より、$n$を$4$で割った余りが$3$のとき、$3^n$を$10$で割った余りは$7$となるから、$n \geqq 2$ のとき$3^{x_n}$を$10$で割った余りは$7$となる。故に$x_{10}$を$10$で割った余りは$7$となる。
（答）$\color{red}{7}$
《コメント》
指数部分の議論がこんがらがってしまいそうですが、誘導が丁寧なのでしっかり解ききりたい問題です。
因みに$N$を整数として、$a_1=1、a_{n+1}=N^{a_n}$ と定義される数列の剰余は大きな$n$で一定値を取ることが知られています。
（出典：東京大学（文科）2016年）