2016年東京大学文系数学大問4

理系数学は難しいけど文系数学なら...と東大に挑戦です。

2016年東京大学文系数学大問4
以下の問いに答えよ。ただし、(1)については、結論のみを書けばよい。
(1)nを正の整数とし、3^n10で割った余りをa_nとする。a_nを求めよ。
(2)nを正の整数とし、3^n4で割った余りをb_nとする。b_nを求めよ。
(3)数列\{x_n\}を次のように定める。
x_1=1,x_{n+1}=3^{x_n}(n=1,2,3,\cdots)
x_{10}10で割った余りを求めよ。


(考察)
(1)は結論だけ書けばいいと言っていますがちゃんと答案を書いているつもりで考えた方がいいと思います。そうすれば(2)にもつながるはず。余りについての問題なので合同式が有効であることは東大受験者は気付かないといけないでしょうね。
(3)は(1)(2)を使うことをとにかく考えます。


(解答)
(1)10を法として
3\equiv3
3^2\equiv9
3^3\equiv27\equiv7
3^4\equiv21\equiv1
3^5\equiv3
以降これが続くので、kを非負整数として

  a_n = \left\{ \begin{array}{ll}
    1 & (n=4k) \\
    3 & (n=4k+1) \\
    9 & (n=4k+2) \\
    7 & (n=4k+3)
  \end{array} \right.


(2)4を法として
3\equiv3
3^2\equiv3\cdot3=9\equiv1
3^3\equiv1\cdot3=3
以降3,1,3,1,\cdotsと続き、答えは

  b_n = \left\{ \begin{array}{ll}
    3 & (nが奇数) \\
    1 & (nが偶数) 
  \end{array} \right.

(3)4を法として
x_2=3^{x_1}=3^1=3
x_3=3^{x_2}=3^3=27\equiv3
よって(2)からx_4=3^{x_3}\equiv3
同様にx_5=3^{x_4}\equiv3
繰り返して
x_{10}=3^{x_9}\equiv3
よってx_{10}=4m+3と表せる整数mが存在し
(1)から10を法としてx_{10}\equiv7となる
故に
x_{10}10で割った余りは7


文系数学としては難しく理系数学としては易しい問題ですかね。難易度調整がすごい。