(1) Note that for the roots $x_{i}$ $(i=1,2)$ of the known equation, we have $x_{i}^{2}=x_{i}+1$. Therefore,
$$\begin{array}{l} a_{n+1}+a_{n}=\frac{x_{1}^{n+1}-x_{2}^{n+1}}{x_{1}-x_{2}}+\frac{x_{1}^{n}-x_{2}^{n}}{x_{1}-x_{2}} \\ =\frac{x_{1}^{n}\left(x_{1}+1\right)-x_{2}^{n}\left(x_{2}+1\right)}{x_{1}-x_{2}} \\ =\frac{x_{1}^{n+2}-x_{2}^{n+2}}{x_{1}-x_{2}} \\ =a_{n+2} . \end{array}$$
(2) Let $a_{i} \equiv b_{i}(\bmod m)\left(0 \leqslant b_{i} \leqslant m-1\right)$.

Then, from $a_{i}=a_{i-1}+a_{i-2}$, we get
$$b_{i} \equiv b_{i-1}+b_{i-2}(\bmod m) \text {. }$$

Therefore, the pair $\left(b_{i}, b_{i+1}\right)$ determines the preceding and succeeding terms, and it is not $(0,0)$ (because if $\left(b_{i}, b_{i+1}\right)=(0,0)$, then by the recurrence formula, the entire sequence modulo $m$ would be 0, which contradicts $a_{1}=a_{2}=1$).
Hence, the possible values of $\left(b_{i}, b_{i+1}\right)$ are $m^{2}-1$.
For $m^{2}$ pairs $\left(b_{i}, b_{i+1}\right)$, by the pigeonhole principle, there must exist $i, j\left(1 \leqslant i<j \leqslant m^{2}\right)$, such that
$$\left(b_{i}, b_{i+1}\right)=\left(b_{j}, b_{j+1}\right) \text {. }$$

Thus, $b_{i}=b_{j}, b_{i+1}=b_{j+1}$.
Let $p=j-i$. Then $b_{k+p}=b_{k}$.
Therefore, $a_{k+p} \equiv a_{k}(\bmod m)$.
Hence, the sequence $\left\{a_{n}\right\}$ is a periodic sequence modulo $m$ with period $p$.
Since $a_{1} \equiv a_{2} \equiv 1(\bmod m)$, we have
$$a_{p+1} \equiv a_{p+2} \equiv 1(\bmod m) \text {. }$$

By the recurrence formula, we get
$$\begin{array}{l} a_{p} \equiv 0(\bmod m), a_{p-1} \equiv 1(\bmod m), \\ a_{p-2} \equiv-1(\bmod m) . \end{array}$$

By periodicity, we have
$$a_{i p-2} \equiv-1(\bmod m)\left(t \in \mathbf{Z}_{+}, t p-2 \geqslant 1\right) \text {. }$$

Let $k=t p-2$, then
$$a_{k}^{4}-2 a_{k} \equiv 3(\bmod m) \text {. }$$

Therefore, for any positive integer $m$, there must exist a positive integer $k$ such that
$$a_{k}^{4}-2 a_{k} \equiv 3(\bmod m) .$$
(Zhang Jialiang, Northwest Normal University High School, 730070)