剰余の問題です。漸化式が絡んでいますが、具体的に考えていけば怖くありません。
《問題》
$n$ を負でない整数とする。以下の問いに答えよ。ただし、（１）については、結論のみを書けばよい。
（１）$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$で割った余りを求めよ。
（東京大学2016 前期文系第４問）
《考え方》
$3^n$を $\text{mod} \ 10$ で並べると$3$、$9 \ (\equiv -1)$、$7 \ (\equiv -3)$、$1$、$\cdots$、と周期$4$で繰り返されるから$k$を自然数として$$\begin{cases} a_{4k-3}=3 \\ a_{4k-2}=9 \\ a_{4k-1}=7 \\ a_{4k}=1 \end{cases}$$となります。
$3^n$は $\text{mod} \ 4$ で表すと$(-1)^n$となるので、$n$が偶数のとき $b_n=1$、$n$が奇数のとき $b_n=3$ となります。
問題は（３）ですね。数列$\{x_n\}$は文字通り桁違いに増加していく数列であるため、やや具体例を考えにくいです。指数表示と合同式を利用して考えましょう。以下、$x_n$を$10$で割った余りを$r_n$と置きます。
$x_1=1$ より $r_1=1$、
$x_2=3$ より $r_2=3$、
$x_3=3^3=27$ より $r_3=7$、
$x_4=3^{27}=9^{13} \cdot 3$ より $r_4 \equiv (-1)^{13} \cdot 3=7$、
$\cdots$、
となります。さて、ここから何かを読み取らなくてはなりません。まず（１）と（２）がヒントになっていることに気付きましょう。（１）の結果から、$n$を$4$で割った余りが分かれば$3^n$を$10$で割った余りが求められます。いま求めたいのは$x_{10}(=3^{x_9})$を$10$で割った余りですから、$x_9(=3^{x_8})$を$4$で割った余りを求めることになります。ここで（２）の結果を利用できることに気付けば、$x_8$は奇数なので$x_9$を$4$で割った余りは$3$と分かります。これは（１）で言う $4k-1$ のときなので、$x_{10}$を$10$で割った余り$r_{10}$は$$7$$と求められました。
（コメント）
誘導設問が有効に機能している良問です。（３）では$x_8$の偶奇が$r_{10}$の決め手となりましたが、これは $n \geqq 3$ のとき一般に成り立つので、 $n \geqq 3$ であれば常に $r_n=7$ となります。
指数型の漸化式は多項式型の漸化式に比べてあまり見かけません。指数型の漸化式で定義される数列$\{a_n\}$は十分大きな$n$を取れば任意の自然数に対する剰余が定数になることが知られています。この事実に関して、例えば1991年のアメリカ合衆国数学オリンピック(USAMO)では底が$2$の指数数列が題材となっています。今回は底が$3$の指数数列が題材で、$10$を法とするとき $n \geqq 3$ で剰余が一定となることを示す問題とも言えます。
･･･当然$10$以外の数でもこれが成立します。少し考察してみましょう。
例として$x_n$を$5$で割った余りを考えてみましょう。
《改題①》
$n$ を負でない整数とする。以下の問いに答えよ。ただし、（１）については、結論のみを書けばよい。
（１）$n$を正の整数とし、$3^n$を$5$で割った余りを$a_n$とする。$a_n$を求めよ。
（２）$n$を正の整数とし、$3^n$を$4$で割った余りを$b_n$とする。$b_n$を求めよ。
（３）数列$\{y_n\}$を次のように定める。
$y_1=1$、$y_{n+1}=3^{y_n} \ (n=1,2,3,\cdots)$
$y_{10}$を$5$で割った余りを求めよ。
（東京大学2016 前期文系第４問 改題①）
《考え方》
$3^n$を $\text{mod} \ 5$ で並べると$3$、$2$、$1$、$3$、$4$、$2$、$1$、$3$、$4$、$\cdots$、となるので $n \geqq 2$ で周期$4$で繰り返されることが分かります。これより$k$を自然数として
$a_1=3$、$\begin{cases} a_{4k-2}=2 \\ a_{4k-1}=1 \\ a_{4k}=3 \\ a_{4k+1}=4 \end{cases} (k \geqq 1)$
となります。$3^n$を$5$で割った余りが周期$4$で循環するのですから、次に考えるのは$3^n$を$4$で割った余りですね。$3^n$を $\text{mod} \ 4$ で並べると$3$、$3$、$1$、$3$、$1$、$\cdots$、と周期$2$で繰り返すので、 $b_1=3$、$n$が偶数のとき $b_n=3$、$n \ (\geqq 3)$が奇数のとき $b_n=1$ となります。
以下、$y_n$を$5$で割った余りを$r’_n$と置きます。
$y_1=1$ より $r’_1=1$、
$y_2=3$ より $r’_2=3$、
$y_3=3^3=27$ より $r’_3=2$、
$y_4=3^{27}=9^{13} \cdot 3$ より $r’_4 \equiv (-1)^{13} \cdot 3=-3 \equiv 2$、
$\cdots$、
となり、$r’_n$は$2$に落ち着きそうです。実際、原題で$r_n$が$7$で一定となることは示していますから、これは正しいことが分かります。したがって$y_{10}$を$5$で割った余りは$2$となります。
次に$7$で割った余りを考えてみます。
《改題②》
$n$ を負でない整数とする。以下の問いに答えよ。ただし、（１）については、結論のみを書けばよい。
（１）$n$を正の整数とし、$3^n$を$7$で割った余りを$a_n$とする。$a_n$を求めよ。
（２）$n$を正の整数とし、$3^n$を$6$で割った余りを$b_n$とする。$b_n$を求めよ。
（３）数列$\{z_n\}$を次のように定める。
$z_1=1$、$z_{n+1}=3^{z_n} \ (n=1,2,3,\cdots)$
$z_{10}$を$7$で割った余りを求めよ。
（東京大学2016 前期文系第４問 改題②）
《考え方》
$3^n$を $\text{mod} \ 7$ で並べると$3$、$6$、$4$、$5$、$1$、$3$、$2$、$\cdots$、となるので $n \geqq 2$ で周期$6$で繰り返されることが分かります。これより$k$を自然数として
$a_1=3$、$\begin{cases} a_{6k-4}=6 \\ a_{6k-3}=4 \\ a_{6k-2}=5 \\ a_{6k-1}=1 \\ a_{6k}=3 \\ a_{6k+1}=2 \end{cases} (k \geqq 1)$
となります。$3^n$を$5$で割った余りが周期$6$で循環しますから、$3^n$を$4$で割った余りを調べます。$3^n$を $\text{mod} \ 6$ で並べると$1$、$3$、$3$、$\cdots$、と$3$で一定になるので、$b_1=1$、$n \geqq 2$ のとき $b_n=3$ となります。
以下、$z_n$を$7$で割った余りを$R_n$と置きます。
$z_1=1$ より $R_1=1$、
$z_2=3$ より $R_2=3$、
$z_3=3^3=27$ より $R_3=6$、
$z_4=3^{27}=(3^4)^{6} \cdot 3^3$ より $R_4 \equiv 4^6 \cdot 6 \equiv 2^3 \cdot 6 =6$、
$\cdots$、
となり、$R_n$は$6$に落ち着きそうです。$z_5=3^{z_4}$ ですが、$z_4$を$6$で割った余りは$3$ですから$z_5$を$7$で割った余りは$6$となります。以下、帰納的に$z_n$を$7$で割った余りは$6$となることが言えますから、$z_{10}$を$7$で割った余りも$6$です。
（コメント）
以上見てきたように、$10$以外の除数についても $3^{3^{3^{\ {\cdot}^{\ {\cdot}^{\ \cdot}}}}}$ の余りが一定になることが言えます。これをすべての自然数に対して証明するのは易しくありませんが、予備知識の一つとして知っておけば、いざというときにワンランク上の問題に対応できるかもしれませんね。
当然、 $4^{4^{4^{\ {\cdot}^{\ {\cdot}^{\ \cdot}}}}}$ とか $7^{7^{7^{\ {\cdot}^{\ {\cdot}^{\ \cdot}}}}}$ についても同じことが言えますが、ここではこれ以上の深入りはしないでおきます。興味のある方は各自の自由研究にしてみてください。