Xét dãy $(y_{n}): y_{n+2}=3y_{n+1}+504y_{n}$ ( $y_{0}=1, y_{1}=45$ ). Dễ thấy $y_{n}\equiv x_{n} (mod 503)$ với mọi số tự nhiên n
Xét phương trình đặc trưng của $(y_{n})$ $y^{2}-3y-504=0 \Leftrightarrow y=24, y=-21$. Kết hợp với $y_{0}=0, y_{1}=45$, công thức số hạng tổng quát của dãy $(y_{n})$ là $y_{n}= 24^{n}-(-21)^{n}$. Vậy $y_{2008}= 24^{2008} -21^{2008}$
Vì 503 là số nguyên tố nên $24^{2008}\equiv (24^{502})^{4}\equiv 1^{4}\equiv 1 (mod 503)$ (định lý Fermat nhỏ). Tương tự $21^{2008}\equiv 1 (mod 503)$. Vậy $y_{2008}\equiv 0 (mod 503)$. Do đó, $x_{2008}\equiv y_{2008}\equiv 0 (mod 503)$.(1)
Xét dãy $(x_{n})$ ta có $x_{k+6}= 3x_{k+5}+x_{k+4}=...= 360x_{k+1}+109x_{k} \Rightarrow x_{k+6}\equiv x_{k} (mod4)$. Vì $2008\equiv 2 (mod 6)$ nên $x_{2008}\equiv x_{2}\equiv 3 (mod4)$ (Do $x_{2}= 3.45$ ) (2). Từ (1) và (2) ta có hệ :
$\left\{\begin{matrix} x_{2008}\equiv 0 (mod 503) & \\ x_{2008}\equiv 3 (mod 4) & \end{matrix}\right.$
Giải hệ trên ta được $x_{2008}\equiv 503 (mod 2012)$.