Bài toán ở dưới đây, là bài Số Học trong đề thi VMO năm 2018 (bài số 6), một bài toán cổ điển về dãy Lucas. Nói chung, bài này tính chất Số Học thì ít mà chủ yếu là màu sắc Đại Số sơ cấp.

Bài toán. Cho dãy số $(x_n)$ xác định bởi $x_0=2,x_1=1$ và $$x_{n+2}=x_{n+1}+x_{n}\left ( n\geq 0 \right ).$$

1. Với $n\geq 1$, chứng minh rằng nếu $x_n$ là số nguyên tố thì $n$ là số nguyên tố hoặc $n$ không có ước nguyên tố lẻ.
2. Tìm các cặp số nguyên không âm $(m,n)$ sao cho $x_n$ chia hết cho $x_m$.

Lời giải. Dãy số trong bài toán trên gọi là dãy Lucas, và tất cả bài toán gói gọn trong công thức sau
\[{x_{m + n}} = {x_m}{x_n} + {\left( { – 1} \right)^{n+1}}{x_{m – n}}\quad\forall\,m;\,n\in\mathbb Z^+, m\ge n\;(*).\]

Công thức này, bạn đọc chứng minh đơn giản nhờ viết ra số hạng tổng quát của dãy Lucas là\[{x_n} = {\left( {\frac{{1 – \sqrt 5 }}{2}} \right)^n} + {\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n}\quad\forall\,n\in\mathbb N.\]
a. Với $n>2k$, ta có
\[{x_n} = {x_{n – k}}{x_k} + {\left( { – 1} \right)^{k+1}}{x_{n – 2k}} \equiv {\left( { – 1} \right)^{k+1}}{x_{n – 2k}}\pmod{x_k}.\]
Từ đây nếu $n=kp$, trong đó $p\in\mathcal P\setminus\{2\}$ và $k>1$ thì
\[{x_n} \equiv {\left( { – 1} \right)^{\frac{{(p – 1)(k+1)}}{2}}}{x_k} \equiv 0\pmod{x_k}.\]
Vì dãy tăng ngặt trên $\mathbb Z^+$ nên $x_k>x_1=1$ và $x_n>x_k$, cho nên $x_n$ không là số nguyên tố.

Vậy nếu $x_n$ là số nguyên tố, thì $n$ là số nguyên tố hoặc $n$ không có ước nguyên tố lẻ.

b. Nếu $m=0$, dễ thấy để $x_m\mid x_n$ thì $3\mid n$, còn $m=1$ thì mọi $n$ đều thoả. Ta xét với $m>1$, khi đó viết phép chia
\[n = qm + r.\]
Ta xét các trường hợp sau:

1. 1. 1. Nếu $q=0$, thì do dãy tăng ngặt trên $\mathbb Z^+$ nên $1\le x_r<x_m$ nên không thoả.
      2. Nếu $q$ chẵn, từ $(*)$ ta có
         \[{x_n} \equiv {\left( { – 1} \right)^{\frac{{q(m+1)}}{2}}}{x_r}\pmod{x_m}\]
         Cho nên không thể có $x_m\mid x_n$, bởi nếu không phải có $x_n\mid x_r$ mà $1\le x_r<x_n$.
      3. Nếu $q$ lẻ, từ $(*)$ ta lại có
         \[{x_n} \equiv {\left( { – 1} \right)^{\frac{{\left( {q – 1} \right){(m+1)}}}{2}}}{x_{m + r}}.\]
         Cho nên để $x_m\mid x_n$ thì $x_m\mid x_{m+r}$
         -Nếu $r>0$, lại để ý đẳng thức
         \[{x_{m + r}} = {x_{2m + r – m}} = {x_r}{x_m} – {\left( { – 1} \right)^r}{x_{m – r}}.\]
         Vậy nếu $x_m\mid x_n$ thì $x_m\mid x_{m-r}$, nhưng điều này là không thể do dãy tăng ngặt trên $\mathbb Z^+$.
         -Nếu $r=0$, tức $n$ là bội lẻ của $m$ thì rõ ràng $x_n\mid x_m$.

Tóm lại, các cặp thoả mãn là $(0;\,3k)$, $(1;\,n)$ và $(m;\,(2k+1)m)$ với $m\in\mathbb Z^+\setminus\{1\},\,n;\,k\in\mathbb N$.

$\square$

Những kiến thức cơ bản về dãy Lucas, bạn đọc có thể tìm hiểu ở https://en.wikipedia.org/wiki/Lucas_sequence hoặc trong cuốn Elementary Number Theory của David Burton.