1.24

设 $g: \mathbb{N} \rightarrow \mathbb{N}$ 满足 $g(0)=0,$ $g(1) = 1,$

$g(n+2) = rs((2002g(n+1)+2003g(n)), 2005)$

(1) 试求 $g(2006)$，

(2) 证明：$g \in \mathcal{EF}$。

证明

先证明(2)，令 $h: \mathbb{N} \rightarrow \mathbb{Z}$ 如下： $h(0) = 0,$ $h(1) = 1,$ $h(n+2) = -3h(n+1)-2h(n)$ 易见 $g(n) = rs(h(n), 2005)$

(注：为何这样构造？$g(n+2) = rs((2005-3)g(n+1)+(2005-2)g(n), 2005)$)

这是因为 $h(n)$ 的特征方程 $\lambda^2= -3\lambda-2$，其根为 $-1, -2$，从而 $h(n)$ 呈形 $a(-1)^n+b(-2)^n$，由 $h(0)=0, h(1) = 1$，故得 $a = 1, b = -1$，因此 $h(n) = (-1)^n-(-2)^n = (-1)^{n+1}(2^n \dot{-}1)$

从而， $g(n) = \left\{ \begin{array}{ll} 2005 \dot{-} rs(2^n \dot{-}1, 2005), & \text{if } n \text{ is even,} \\ rs(2^n \dot{-}1, 2005), & \text{if } n \text{ is odd.} \end{array}\right.$

$g(n) = (2005 \dot{-}rs(2^n\dot{-}1, 2005) Nrs(n,2)) + rs(2^n\dot{-}1, 2005)N^2rs(n,2)$

故 $g \in \mathcal{EF}$。

再计算(1)，$2005 = 5 \times 401$，$5, 401$ 均为素数

由Fermat's little theorem（费马小定理：假如 $p$ 是素数，且 $(a,p) =1$，那么 $a^{p-1} \equiv 1 (\text{mod } p)$)知，

$2^4 \equiv 1 \mod 5, 2^{400} \equiv 1 \mod 401$

$\because (5, 401) = 1, \therefore 2^{400} \equiv 1(\text{mod }5 \times 401)$，即 $rs(2^{400}, 2005) = 1$

从而，$g(n+400) = g(n)$，$g$ 的周期为 $400$

故 $g(2006) = g(6) = rs(h(6), 2005)) = 2005 \dot{-} rs(2^6-1, 2005) = 1942$。