OMC105(E)

【公式解説を一般化し, $n\geq2$ に対して $a_n \equiv 27 \pmod{82}$ であることを示す.】

$3^8\equiv1\pmod{82}$ より, $a_n\mod{8}$ について考える. 帰納的に $a_n$ は正の奇数であるから, 非負整数 $k_n$ を用いて, $a_n=2k_n+1$ と表せる. よって, $$a_{n+1}=3^{2k_n+1}=9^{k_n} \times 3 \equiv 1^{k_n} \times 3 = 3 \pmod{8}$$ および $a_1=3\equiv3\pmod{8}$ より, $n \geq 1$ に対して $a_n \equiv 3\pmod{8}$.

よって, 非負整数 $l_n$ を用いて, $a_n=8l_n+3$ と表せる. 以上より, $$a_{n+1}=3^{8l_n+3}=\left(3^8\right)^{l_n} \times 27 \equiv 1^{l_n} \times 27=27\pmod{82}$$ すなわち, $n\geq2$ に対して, $a_n \equiv 27 \pmod{82}$ である.