Cho dãy số nguyên $(u_n)$ được xác định bởi $u_1=3,u_2=7$ và
$$u_{n+2}=3u_{n+1}-u_n,\forall n\ge 1.$$
Cho $N$ là hợp số lẻ không chia hết cho 3 và $u_N\equiv 3(\mathrm{mod}N)$. Đặt $M=\frac{u_N}{3}$.
a) Chứng minh rằng $u_N$ chia hết cho 3 nhưng không chia hết cho 9.
b) Chứng minh rằng $M\equiv 1(\mathrm{mod}4N)$ và $M$ là một hợp số.

a) Để ý vì $u_{n+2}\equiv -u_n(\mathrm{mod}3)$ và $3\mid u_1$ nên $3\mid u_n$ với mọi $n$ lẻ.

Xét dãy $(v_n)$ xác định bởi $v_n=\frac{u_{2n+1}}{3}$ với mọi số tự nhiên $n$.

Khi đó $u_{n+4}=3u_{n+3}-u_{n+2}=3(3u_{n+2}-u_{n+1})-u_{n+2}=8u_{n+2}-(u_{n+2}+u_n)=7u_{n+2}-u_n$.

Suy ra $v_0=1$, $v_1=6$ và $v_{n+2}=7v_{n+1}-v_n$ với mọi số tự nhiên $n$.

Để ý $v_n$ chia hết cho 3 khi và chỉ khi $n\equiv 1,4(\mathrm{mod}6)$, hay $n\equiv 1(\mathrm{mod}3)$.

Viết $N=2k+1$ với $k$ nguyên dương thì $2k+1\not\equiv 0(\mathrm{mod}3)$ nên $k\not\equiv 1(\mathrm{mod}3)$ nên $3\nmid v_k$.

Từ đó $u_N=u_{2k+1}=3v_k$ không chia hết cho 9, điều phải chứng minh.

b) Ta cần chứng minh $v_k\equiv 1(\mathrm{mod}4N)$ và $v_k$ là hợp số.

Vì $u_N\equiv 3(\mathrm{mod}N)$ nên $3v_k\equiv 3(\mathrm{mod}N)$ nên $v_k\equiv 1(\mathrm{mod}N)$ do $\gcd (N,3)=1$.

Ta có $v_n\equiv 1(\mathrm{mod}4)⟺n\equiv 0,2(\mathrm{mod}3)$.

Vì $k\not\equiv 1(\mathrm{mod}3)$ nên $v_k\equiv 1(\mathrm{mod}4)$, kết hợp $\gcd (N,4)=1$ để có $v_k\equiv 1(\mathrm{mod}4N)$.

Đặt $\alpha =\frac{3+\sqrt{5}}{2}$ và $\beta =\frac{3-\sqrt{5}}{2}$ thì $u_n={\alpha }^n+{\beta }^n$ với mọi $n$ nguyên dương.

Ta có $N=ab$ với $a,b>1$ là các số lẻ thì dễ dàng thấy được $u_N$ chia hết cho $u_a$.

Vì thế $M=\frac{u_N}{3}=\frac{u_N}{u_b}\cdot \frac{u_b}{3}$ là hợp số do $\frac{u_b}{3}$ là số nguyên lớn hơn 1 và $u_N>u_b$.

Từ đó ta có điều phải chứng minh.