解説

方針・初手

余りが $1$ であることは、合同式を用いて

$$ a_n \equiv 1 \pmod{3^n}

$$

と表せる。これを数学的帰納法で示す。

漸化式が $a_{n+1}=a_n^3$ なので、$a_k=1+3^k m$ とおいたとき、$a_{k+1}=a_k^3$ が $3^{k+1}$ で割って $1$ 余る形になることを確認する。

解法1

命題 $P(n)$ を

$$ a_n \equiv 1 \pmod{3^n}

$$

とする。すなわち、ある整数 $q$ を用いて

$$ a_n=3^n q+1

$$

と表せることを示す。

まず $n=1$ のとき、

$$ a_1=7=3\cdot 2+1

$$

であるから、

$$ a_1 \equiv 1 \pmod{3}

$$

となる。よって $P(1)$ は成り立つ。

次に、ある自然数 $k$ に対して $P(k)$ が成り立つと仮定する。このとき、ある整数 $m$ が存在して

$$ a_k=1+3^k m

$$

と表せる。

漸化式より、

$$ a_{k+1}=a_k^3=(1+3^k m)^3

$$

である。これを展開すると、

$$ \begin{aligned} a_{k+1} &=1+3\cdot 3^k m+3(3^k m)^2+(3^k m)^3 \\ &=1+3^{k+1}m+3^{2k+1}m^2+3^{3k}m^3 \end{aligned}

$$

となる。

ここで $k\geqq 1$ であるから、

$$ 2k+1\geqq k+1,\qquad 3k\geqq k+1

$$

が成り立つ。したがって、

$$ 3^{k+1}m,\quad 3^{2k+1}m^2,\quad 3^{3k}m^3

$$

はいずれも $3^{k+1}$ で割り切れる。

よって、ある整数 $M$ が存在して

$$ a_{k+1}=1+3^{k+1}M

$$

と書ける。したがって、

$$ a_{k+1}\equiv 1 \pmod{3^{k+1}}

$$

であり、$P(k+1)$ が成り立つ。

以上より、数学的帰納法によって、すべての自然数 $n$ について

$$ a_n\equiv 1 \pmod{3^n}

$$

が成り立つ。

解説

この問題では、$a_n$ を直接求める必要はない。求めたいのは $3^n$ で割った余りなので、合同式で扱うのが自然である。

重要なのは、帰納法の仮定を

$$ a_k=1+3^k m

$$

という形で使うことである。この形にしておけば、$a_{k+1}=a_k^3$ を展開したときに、$3^{k+1}$ の倍数が現れることを確認できる。

特に、$a_k\equiv 1\pmod{3^k}$ からすぐに $a_k^3\equiv 1\pmod{3^{k+1}}$ と断定してはいけない。法が $3^k$ から $3^{k+1}$ に強くなっているため、展開して $3^{k+1}$ の倍数になることを確かめる必要がある。

答え

すべての自然数 $n$ について、

$$ a_n\equiv 1 \pmod{3^n}

$$

が成り立つ。

したがって、$a_n$ を $3^n$ で割ったときの余りは $1$ である。