问题及解答

一个正整数数列 $\{a_n\}$,  $a_1=8$, $a_2=1$, 当 $n\geqslant 3$ 时, 满足 $a_n=a_{n-1}+a_{n-2}$. 问 $a_{2018}$ 被 105 除的余数是多少？
 

由递推公式 $a_{k}=a_{k-1}+a_{k-2}$, $k\geqslant 3$ 可推出

\[
\sum_{k=3}^n a_{k}=\sum_{k=3}^n a_{k-1}+\sum_{k=3}^n a_{k-2}
\]

推出

\[
a_n=a_2+\sum_{k=3}^n a_{k-2}=1+\sum_{k=1}^{n-2} a_{k}
\]

即, 对 $n\geqslant 3$, 有

\[
a_n=1+\sum_{i=1}^{n-2}a_i
\]

于是

\[
\begin{split}
a_n&=1+\sum_{i=1}^{n-2}a_i\\
&=1+a_{n-2}+a_{n-3}+\sum_{i=1}^{n-4}a_i\\
&=1+(1+\sum_{i=1}^{n-4}a_i)+a_{n-3}+\sum_{i=1}^{n-4}a_i\\
&=2+a_{n-3}+2\sum_{i=1}^{n-4}a_i\\
\end{split}
\]

于是推出 $a_n\equiv a_{n-3}\pmod 2$.

我们继续进行演算

\[
\begin{split}
a_n&=2+a_{n-3}+2\sum_{i=1}^{n-4}a_i\\
&=2+(1+\sum_{i=1}^{n-5}a_i)+2a_{n-4}+2\sum_{i=1}^{n-5}a_i\\
&=3+2a_{n-4}+3\sum_{i=1}^{n-5}a_i\\
\end{split}
\]

这推出 $a_n\equiv 2a_{n-4}\pmod 3$, 从而

\[
a_n\equiv 2^2 a_{n-8}\equiv a_{n-8}\pmod 3
\]

继续进行演算

\[
\begin{split}
a_n&=3+2a_{n-4}+3\sum_{i=1}^{n-5}a_i\\
&=3+2(1+\sum_{i=1}^{n-6}a_i)+3a_{n-5}+3\sum_{i=1}^{n-6}a_i\\
&=5+3a_{n-5}+5\sum_{i=1}^{n-6}a_i
\end{split}
\]

这推出 $a_n\equiv 3a_{n-5}\pmod 5$, 从而

\[
a_n\equiv 3^2 a_{n-10}\equiv 3^3 a_{n-15}\equiv 3^4 a_{n-20}\equiv a_{n-20}\pmod 5
\]

即 $a_n\equiv a_{n-20}\pmod 5$.

 

继续进行演算

\[
\begin{split}
a_n&=5+3a_{n-5}+5\sum_{i=1}^{n-6}a_i\\
&=5+3(1+\sum_{i=1}^{n-7}a_i)+5a_{n-6}+5\sum_{i=1}^{n-7}a_i\\
&=8+5a_{n-6}+8\sum_{i=1}^{n-7}a_i
\end{split}
\]

这推出 $a_n\equiv 5a_{n-6}\pmod 8$, 从而

\[
a_n\equiv 5^2 a_{n-10}\equiv a_{n-12}\pmod 8
\]

即 $a_n\equiv a_{n-12}\pmod 8$.

 

继续进行演算

\[
\begin{split}
a_n&=8+5a_{n-6}+8\sum_{i=1}^{n-7}a_i\\
&=8+5(1+\sum_{i=1}^{n-8}a_i)+8a_{n-7}+8\sum_{i=1}^{n-8}a_i\\
&=13+8a_{n-7}+13\sum_{i=1}^{n-8}a_i
\end{split}
\]

这推出 $a_n\equiv 8a_{n-7}\pmod {13}$, 从而

\[
a_n\equiv 8^2 a_{n-14}\equiv 8^3 a_{n-21}\equiv 8^4 a_{n-28}\equiv a_{n-28}\pmod {13}
\]

即 $a_n\equiv a_{n-28}\pmod {13}$.

 

继续进行演算

\[
\begin{split}
a_n&=13+8a_{n-7}+13\sum_{i=1}^{n-8}a_i\\
&=13+8(1+\sum_{i=1}^{n-9}a_i)+13a_{n-8}+13\sum_{i=1}^{n-9}a_i\\
&=21+13a_{n-8}+21\sum_{i=1}^{n-9}a_i
\end{split}
\]

这推出 $a_n\equiv 13a_{n-8}\pmod {21}$, 从而

\[
a_n\equiv {13}^2 a_{n-16}\equiv a_{n-16}\pmod {21}
\]

即 $a_n\equiv a_{n-16}\pmod {21}$.

 

---

 

用归纳法容易证明

\[
a_n=F_k+F_{k-1}a_{n-k}+F_k\sum_{i=1}^{n-(k+1)}a_i.
\]

于是

\[
a_{2018}\equiv 3 a_{2018-5}\equiv {3}^2 a_{2018-5\times 2}\equiv\cdots\equiv {3}^s a_{2018-5\times s}\pmod {5},
\]

令 $s=403$, 则得

\[
a_{2018}\equiv {3}^{403}a_3\equiv {3}^{403}\cdot 9\equiv 3^{405}\pmod {21}.
\]

注意到

\[
3^n\equiv\begin{cases}
3, & n=4k+1,\\
4, & n=4k+2,\\
2, & n=4k+3,\\
1, & n=4k
\end{cases}\quad\pmod 5
\]

故 $a_{2018}\equiv 3^{405}\equiv 3\pmod 5$.

类似的, 有

\[
a_{2018}\equiv 13 a_{2018-8}\equiv {13}^2 a_{2018-8\times 2}\equiv\cdots\equiv {13}^t a_{2018-8\times t}\pmod {21},
\]

令 $t=252$, 则得

\[
a_{2018}\equiv {13}^{252}a_2\equiv {13}^{252}\equiv 1\pmod {21}.
\]

---

 

现在问题化为一个同余方程组

\[
\begin{cases}
x\equiv 3\pmod 5,\quad(1)\\
x\equiv 1\pmod {21}.\quad(2)
\end{cases}
\]

我们解得 $x\equiv 43\pmod {105}$.

参见问题2031