Các bài toán về dãy số nguyên

Bổ đề quan trọng

(Biểu thức cổ định của dãy tuyến tính cấp hai) Cho dãy số \( (a_n) \) xác định bởi \[ a_{n+2} = aa_{n+1} - a_n +b\quad \forall n \in \mathbb{N}. \]

Khi đó, biểu thức \( a_{n+1}^2 - a_n a_{n+2}-ba_{n+1} \) luôn nhận giá trị không đổi.

Chứng minh.

Thật vậy, ta có biến đổi sau

\[ \begin{align} x_{n+1}^2 - x_n x_{n+2} - b x_{n+1} &= x_{n+1}(x_{n+1} - b) - x_n(a x_{n+1} - x_n + b) \\ &= x_{n+1}(a x_n - x_{n-1}) - x_n(a x_{n+1} - x_n + b) \\ &= x_n^2 - x_{n-1} x_{n+1} - b x_n \end{align} \]

Đẳng thức trên đúng với mọi \( n \geq 0 \) nên

\[ x_{n+1}^2 - x_n x_{n+2} - b x_{n+1} = x_1^2 - x_0 x_2 - b x_1 = \text{const.} \]

Bổ đề quan trọng

(Về sự tuần hoàn của các số dư) Cho dãy số nguyên \(\{x_n\}\) xác định bởi công thức truy hồi \[ x_{n+k} = a_1 x_{n+k-1} + \ldots + a_k x_n \] và \(k\) số hạng đầu tiên nguyên. Khi đó, với mọi số nguyên dương \(N\), dãy số dư của \(x_n\) khi chia cho \(N\) sẽ tuần hoàn kể từ một lúc nào đó. Tức là tồn tại \(n_0\) đủ lớn và \(T\) nguyên dương sao cho : \[ x_{n+T}\equiv x_n\pmod N\ \text{với mọi}\ n\geq n_0 \] Đặc biệt, nếu \(gcd(a_k,N)=1\) thì dãy số dư của \(x_n\) khi chia cho \(N\) sẽ tuần hoàn. Tức là tồn tại \(T\) nguyên dương sao cho : \[ x_{n+T}\equiv x_n\pmod N\ \text{với mọi}\ n \]

Chứng minh.

Xét \( N^k + 1 \) bộ số dư của \( (x_i, x_{i+1}, \ldots, x_{i+k-1}) \), với \( 1 \leq i \leq N^k+1 \) khi chia cho \( N \). Ta có tối đa \( N^k \) bộ phân biệt như vậy, do đó theo nguyên lý Dirichlet thì có \( j, l \) phân biệt mà

\[ x_{j+i} \equiv x_{l+i} \pmod{N} \quad \forall i = \overline{1, k-1}. \]

Từ đây, ta suy ra

\[ x_{j+i} \equiv x_{l+i} \pmod{N} \quad \forall i. \] và \[ a_k x_{j-1} \equiv a_k x_{l-1} \pmod{N}, \]

Nếu \(gcd(a_k,N)=1\) thì \( x_{j-1} \equiv x_{l-1} \pmod{N} \). Cứ tiếp tục như vậy, ta thu được \( T := |j - l| \) là chu kì cần tìm.

Bài toán (VMO 2019-2020)

Cho dãy số \((a_n)\) xác định bởi \(a_1 = 5, a_2 = 13\) và \(a_{n+2} = 5a_{n+1} - 6a_n\) với mọi \(n \geq 2\).

a) Chứng minh rằng hai số hạng liên tiếp của dãy trên nguyên tố cùng nhau.

b) Chứng minh rằng nếu \(p\) là ước nguyên tố của \(a_{2^k}\) thì \(p-1\) chia hết cho \(2^{k+1}\) với mọi số tự nhiên \(k\).

Lời giải. a) Cách 1. Ta thấy \((a_n)\) là dãy sai phân tuyến tính cấp hai có phương trình đặc trưng \(x^2 = 5x - 6\) với hai nghiệm là \(x_1 = 2\), \(x_2 = 3\) nên dễ dàng tìm được công thức tổng quát là

\[ a_n = 2^n + 3^n, \forall n. \]

Đến đây, giả sử có \(n \geq 1\) để \(a_n\), \(a_{n+1}\) có ước nguyên tố chung là \(p\). Rõ ràng \(\gcd(p, 6) = 1\). Ta có

\[ \begin{cases} p \mid 2^n + 3^n \\ p \mid 2^{n+1} + 3^{n+1} \end{cases} \rightarrow \begin{cases} p \mid 3 \cdot 2^n + 3^{n+1} \\ p \mid 2 \cdot 2^n + 3^{n+1} \end{cases}\rightarrow p \mid 2^n, \]

vô lý vì \(\gcd(p, 6) = 1\).

Cách 2. Vì \(a_{n+2} \equiv 5a_{n+1} \pmod{6}\) và \(a_1 = 5\), \(a_2 = 13\) nên các số hạng của dãy luôn nguyên tố cùng nhau với 6. Giả sử tồn tại số nguyên tố \(p \geq 5\) để \(p \mid a_n\), \(a_{n+1}\) với \(n \in \mathbb{Z}^+\). Suy ra

\[ p \mid 5a_n - 6a_{n-1} \rightarrow p \mid 6a_n \rightarrow p \mid a_{n-1}. \]

Từ đó thực hiện liên tiếp thao tác này thì suy ra \(p \mid a_1\), \(a_2\), vô lý vì \(\gcd(a_1, a_2) = 1\).

b) Bổ đề. Cho \( a \) và \( b \) là các số nguyên tố cùng nhau và \( n \) là một số nguyên dương. Chứng minh rằng bất kỳ ước số dương lẻ nào của \( a^{2^n} + b^{2^n} \) đều đồng dư với 1 modulo \( 2^{n+1} \).

Chứng minh. Ta chỉ cần chứng minh rằng bất kỳ ước nguyên tố lẻ \( p \) nào của \( a^{2^n} + b^{2^n} \) đều đồng dư với 1 modulo \( 2^{n+1} \). Lưu ý rằng \( p \) không là ước của \( ab \), vì \( \gcd(a, b) = 1 \). Gọi \( c \) là một số nguyên sao cho \( bc \equiv 1 \pmod{p} \), khi đó \( p \) là ước của \( (ac)^{2^n} + 1 \). Khi đó, \( k = ord_p(ac)\) là ước của \( 2^{n+1} \), vì \( p \) là ước của \( (ac)^{2^{n+1}} - 1 \), và không là ước của \( 2^n \), vì nếu không ta sẽ có \( p \) là ước của \( (ac)^{2^n} - 1 \) và \( p \) là ước của \( (ac)^{2^n} + 1 - ((ac)^{2^n} - 1) = 2 \), điều này mâu thuẫn. Do đó, \( k = 2^{n+1} \) và vì \( k \) là ước của \( p - 1 \), ta hoàn thành chứng minh.

Áp dụng bổ đề ta có ngay điều phải chứng minh.

Bài toán (VMO 2024-2025)

Với mỗi số nguyên \( n \geq 0 \), đặt \( u_n = \left( 2 + \sqrt{5} \right)^n + \left( 2 - \sqrt{5} \right)^n \).

a) Chứng minh rằng \( u_n \) là số nguyên với mọi \( n \geq 0 \). Khi \( n \) thay đổi, số dư của \( u_n \) khi chia cho 24 lớn nhất bằng bao nhiêu?

b) Tìm tất cả các cặp số nguyên \( (a, b) \) với \( a, b \) nhỏ hơn 500 sao cho với mọi \( n \) lẻ ta có \( u_n \equiv a^n - b^n \) (mod 1111).

Lời giải. a) Từ giả thiết, ta dễ dàng chứng minh được u_n+2 = 4u_n+1 + u_n với mọi số tự nhiên n. Đến đây, bằng tính toán trực tiếp, ta dễ thấy dãy số dư khi chia các số hạng của dãy (u_n) cho 24 tuần hoàn theo chu kỳ 8: 2, 4, 18, 4, 10, 20, 18, 20. Như vậy, khi n thay đổi, số dư của u_n khi chia cho 24 lớn nhất là 20.

b) Xét một cặp số (a, b) thỏa mãn yêu cầu đề bài. Cho n = 1 và n = 3, ta được a−b ≡ 4 (mod 1111) và a³ − b³ ≡ 76 (mod 1111). Từ đó

76 ≡ (a − b)³ + 3ab(a − b) ≡ 64 + 12ab (mod 1111).

Suy ra ab ≡ 1 (mod 1111), hay b(b + 4) ≡ 1 (mod 1111). Một cách tương đương, ta có

(b + 2)² ≡ 5 (mod 1111).

Từ đó (b + 2)² ≡ 5 (mod 11) và (b + 2)² ≡ 5 (mod 101).

Vì (b + 2)² ≡ 5 ≡ 16 (mod 11) nên b ≡ 2, 5 (mod 11).

Vì (b + 2)² ≡ 5 ≡ 45² (mod 101) nên b ≡ 43, 54 (mod 101).

Kết hợp hai kết quả lại, ta suy ra b phải có một trong các dạng 1111k + 750, 1111k + 761, 1111k + 346 hoặc 1111k + 357 với k nguyên. Mà 1 ≤ b < 500 nên b ∈ {346, 357}. Kết hợp với a ≡ b (mod 1111) và 1 ≤ a < 500, ta được (a, b) ∈ {(350, 346), (361, 357)}.

Bây giờ, ta sẽ chứng minh hai cặp số (350, 346) và (361, 357) thỏa mãn yêu cầu đề bài. Dễ thấy với hai cặp số (a, b) như trên, ta có a² ≡ 4a + 1 (mod 1111) và b² ≡ −4b + 1 (mod 1111). (Ta có thể suy ra điều này từ a − b ≡ 4 (mod 1111) và ab ≡ 1 (mod 1111) mà không phải tính toán gì.)

Bằng quy nạp, ta sẽ chứng minh với mọi số tự nhiên m, thì u_2m+1 ≡ a^2m+1 − b^2m+1 (mod 1111) với mọi số nguyên dương n lẻ và u_2m = a^2m + b^2m (mod 1111). Với m = 0 và m = 1, khẳng định hiển nhiên đúng. Giả sử khẳng định đúng đến m với m nguyên dương. Sử dụng giả thiết quy nạp, ta có

u_2m+2 = 4u_2m+1 + u_2m = 4(a^2m+1 − b^2m+1) + a^2m + b^2m
= (4a + 1)a^2m + (1 − 4b)b^2m ≡ a^2m+2 + b^2m+2 (mod 1111).

Từ đó

u_2m+3 = 4u_2m+2 + u_2m+1 = 4(a^2m+2 + b^2m+2) + a^2m+1 − b^2m+1
= (4a+1)a^2m+1 + (4b − 1)b^2m+1 ≡ a^2m+3 − b^2m+3 (mod 1111).

Như vậy, khẳng định cũng đúng với m + 1. Theo nguyên lý quy nạp, ta có khẳng định đúng với mọi số tự nhiên m.

Vậy, có hai cặp số thỏa mãn yêu cầu đề bài là (350, 346) và (361, 357).

Bài toán (Poland Finals 2002)

Cho \( k \) là một số nguyên dương cố định. Xét dãy \((a_n)\) thỏa mãn :

\[ \begin{cases} a_1 = k + 1 \\ a_{n+1} = a_n^2 - k a_n + k, \quad \forall n \geq 1 \end{cases} \]

Chứng minh rằng với mọi số nguyên dương \( m \) khác \( n \) thì \( a_m, a_n \) nguyên tố cùng nhau.

Lời giải

Ta có :

\[ a_{n+1} - k = a_n(a_n - k) = a_na_{n-1}(a_{n-1} - k) = \ldots = a_na_{n-1}a_{n-2}\ldots a_1(a_1 - k) = a_na_{n-1}\ldots a_1 \]

Không giảm tổng quát, ta giả sử \( m > n \). Khi đó gọi \( p \) là một ước nguyên tố chung của \(\gcd(a_m, a_n)\). Ta có :

\[ a_m - k = a_{m-1}a_{m-2}\ldots a_{n-1}a_1 : p \Rightarrow p \mid k \]

Suy ra :

\[ p \mid a_n - k = a_{n-1}(a_{n-1} - k) = a_{n-1}^2 - ka_{n-1} \Rightarrow p \mid a_{n-1}^2 \Rightarrow p \mid a_{n-1} \]

Và lại suy ra :

\[ p \mid a_{n-1} - k = a_{n-2}^2 - ka_{n-2} \Rightarrow p \mid a_{n-2}^2 \Rightarrow p \mid a_{n-2} \]

Cứ tiếp tục quá trình này ta suy ra \( p \mid a_1 = k + 1 \), suy ra \( p \mid 1 \). Mâu thuẫn.

Như vậy \(\gcd(a_m, a_n)\) không có một ước nguyên tố nào, tức là \(\gcd(a_m, a_n) = 1\). Điều phải chứng minh.

Bài toán

Xét dãy số \((a_n)\) thỏa mãn:

\[ \begin{cases} a_0 = 0, & a_1 = 1, a_2 = 2, a_3 = 6 \\ a_{n+4} = 2a_{n+3} + a_{n+2} - 2a_{n+1} - a_n \end{cases} \]

a) Chứng minh rằng với mọi số nguyên dương \(n\) thì \(n \mid a_n\).

b) Chứng minh rằng với \(k\) là số nguyên dương bất kỳ thì dãy \(\frac{a_1}{1}, \frac{a_2}{2}, \frac{a_3}{3}, \ldots, \frac{a_n}{n}\) chứa vô hạn các số hạng chia hết cho \(k\).

Lời giải

a) Ta thấy

\[ \frac{a_1}{1} = 1 = F_{1}, \quad \frac{a_2}{2} = 1 = F_{2}, \quad \frac{a_3}{3} = 2 = F_{3}, \quad \frac{a_4}{4} = 3 = F_{4}, \quad \frac{a_5}{5} = 5 = F_{5}, \ldots \]

Vậy ta có dự đoán:

\[ a_n = n \cdot F_n \]

Và chứng minh dự đoán này bằng quy nạp, giả sử điều đó đúng đến \(n + 3\). Xét với \(n + 4\):

\[ \begin{aligned} a_{n+4} &= 2a_{n+3} + a_{n+2} - 2a_{n+1} - a_n \\ &= 2(n + 3)F_{n+3} + (n + 2)F_{n+2} - 2(n + 1)F_{n+1} - nF_n \\ &= 2(n + 3)F_{n+3} + (n + 2)F_{n+2} - 2(n + 1)F_{n+1} - n(F_{n+2} - F_{n+1}) \\ &= 2(n + 3)F_{n+3} + 2F_{n+2} - (n + 2)F_{n+1} \\ &= 2(n + 3)F_{n+3} + 2F_{n+2} - (n + 2)(F_{n+3} - F_{n+2}) \\ &= (n + 4)(F_{n+3} + F_{n+2}) \\ &= (n + 4)F_{n+4} \end{aligned} \]

Theo nguyên lí quy nạp ta có \(a_n = n \cdot F_n\) với mọi \(n\) nguyên dương, suy ra \(n \mid a_n\) với mọi \(n\) nguyên dương.

Điều phải chứng minh.

b) Nhận thấy dãy nói ở đề bài chính là dãy Fibonacci.

Từ đó theo định luật tuần hoàn của dãy số dư, ta có dãy số dư \((r_n)\) là dãy tuần hoàn. Trong đó \(r_n\) là số dư khi chia \(F_n\) cho \(k\) với mỗi \(n\). Hơn nữa \(r_0 = 0\) vì \(F_0 = 0\), điều này đồng nghĩa tồn tại vô hạn số hạng của dãy Fibonacci là bội của \(k\). Điều phải chứng minh.

Bài toán (China 1991)

Cho dãy số \( (u_n) \) nguyên thỏa mãn \( u_{n+2} = u_{n+1}^2 - u_n \) với mọi \( n \) tự nhiên. Giả sử \( u_0 = 39, u_1 = 45 \).

Chứng minh có vô hạn số hạng của dãy \( (u_n) \) chia hết cho 1986.

Lời giải

Gọi \( r_n \) là số dư của \( u_n \) khi chia cho 1986 ứng với mỗi \( n \). Ta chứng minh dãy \( (r_n) \) tuần hoàn.

Xét dãy gồm các bộ số dư :

\[ (r_1, r_2), \, (r_2, r_3), \, \ldots, \, (r_m, r_{m+1}), \, \ldots \]

Dãy trên có vô số số hạng mà số bộ khác nhau là hữu hạn vì \( r_i \in \{0, 1, 2, \ldots, 1985\} \). Như vậy theo nguyên lí Dirichlet, sẽ tồn tại hai bộ trùng nhau. Tức là tồn tại \( k, m \) nguyên dương :

\[ (r_{m+1}, r_{m+2}) = (r_{m+k+1}, r_{m+k+2}) \]

Từ đó :

\[ r_m = r_{m+1}^2 - r_{m+2} = r_{m+k+1}^2 - r_{m+k+2} = r_{m+k} \] \[ r_{m-1} = r_{m}^2 - r_{m+1} = r_{m+k}^2 - r_{m+k+1} = r_{m+k-1} \] \[...\] \[ r_1 = r_2^2 - r_3 = r_{k+2}^2 - r_{k+3} = r_{k+1} \]

Tức là ta đã được :

\[ (r_1, r_2) = (r_{k+1}, r_{k+2}) \]

Từ đó dựa vào công thức xác định dãy, ta thu được :

\[ r_n = r_{n+k}, \, \forall n = 0, 1, 2, \ldots \]

Hơn nữa ta có \( u_2 = 45^2 - 39 = 1986 \) nên sẽ tồn tại vô hạn số hạng của dãy \( (u_n) \) chia hết cho 1986.

Bài toán (VMO 2022-2023)

Cho các số nguyên \( a, b, c, \alpha, \beta \) và dãy số \((u_n)\) xác định bởi

\[ u_1 = \alpha, \, u_2 = \beta, \, u_{n+2} = a u_{n+1} + b u_n + c \, \text{với mọi } n \geq 1. \]

Chứng minh rằng tồn tại số nguyên dương \( n_0 \) sao cho có duy nhất một trong hai khẳng định sau là đúng:

i) Có vô số số nguyên dương \( m \) để

\[ u_{n_0} \, u_{n_0+1} \cdots u_{n_0+m} \, \text{chia hết cho } 7^{2023} \, \text{hoặc } 17^{2023}, \]

ii) Có vô số số nguyên dương \( k \) để

\[ u_{n_0} \, u_{n_0+1} \cdots u_{n_0+k} - 1 \, \text{chia hết cho } 2023. \]

Chứng minh

Giả sử trong dãy \( (u_n) \) tồn tại vô số số chia hết cho 7 hoặc tồn tại vô số số chia hết cho 17. Khi đó, \( u_1 \cdot u_2 \cdot \ldots \cdot u_n \) chia hết cho \( 7^{2023} \) hoặc \( 17^{2023} \) với mọi số nguyên dương \( n \) đủ lớn, và với mọi số dương \( n \) đủ lớn đó, \( u_1 \cdot u_2 \cdot \ldots \cdot u_n - 1 \) không chia hết cho \( 2023 = 7 \cdot 17^2 \). Do đó, lấy \( n_0 = 1 \) thì khẳng định i) đúng và khẳng định ii) sai.

Bây giờ ta xét trường hợp dãy \( (u_n) \) không có hoặc có hữu hạn số chia hết cho 7 hoặc 17, tức là, \( u_n \) nguyên tố cùng nhau với 2023, với mọi \( n \) đủ lớn.

Gọi \( r_n \) là số dư khi chia \( u_n \) cho 2023. Khi đó, tồn tại số nguyên dương \( n_1 \) để \( (r_n, 2023) = 1 \) với mọi \( n \geq n_1 \). Các cặp số \( (r_n, r_{n+1}) \) chỉ nhận hữu hạn khả năng, do đó, theo Nguyên lý Dirichlet, tồn tại các số nguyên dương \( n_0, s \) (\( n_0 > n_1 \)) sao cho

\[ (r_{n_0}, r_{n_0 + 1}) = (r_{n_0 + s}, r_{n_0 + s + 1}). \]

Với \( n_0 \) đã chọn, rõ ràng i) không đúng.

Với mọi số nguyên dương \( m \), ta có \( r_{n_0 + m} = r_{n_0 + r(m)} \), với \( r(m) \) là số dư khi chia \( m \) cho \( s \).

Lấy \( k = \varphi(2023) \cdot t \cdot s - 1 \) với \( t \) là số nguyên dương tùy ý, (\( \varphi \) là hàm Euler). Khi đó,

\[ \begin{align} u_{n_0} \cdot u_{n_0 + 1} \cdot \ldots \cdot u_{n_0 + k} &\equiv r_{n_0} \cdot r_{n_0 + 1} \cdot \ldots \cdot r_{n_0 + \varphi(2023) \cdot t \cdot s - 1} \\ &= (r_{n_0})^{\varphi(2023) \cdot t} \cdot (r_{n_0 + 1})^{\varphi(2023) \cdot t} \cdot \ldots \cdot (r_{n_0 + s - 1})^{\varphi(2023) \cdot t} \\ &\equiv 1 \pmod{2023}. \end{align} \]

Bài toán

Cho dãy số nguyên \( (a_n) \) xác định bởi

\[ a_1 = a, \quad a_2 = b, \quad a_n = 6a_{n-1} - a_{n-2} \quad \forall n \geq 3. \]

Hãy tìm tất cả các số nguyên dương \( p \) sao cho tồn tại cặp số \( (a, b) \) nguyên thỏa mãn \( p + 4a_n a_{n+1} \) là số chính phương với mọi \( n \).

Lời giải.

Theo tính chất quen thuộc của dãy số nguyên, ta có

\[ a_{n+1}^2 - a_n a_{n+2} = a_n^2 - a_{n-1} a_{n+1} = \ldots = a_2^2 - a_3 a_1 = b^2 - 6ab + a^2. \]

Từ đó, ta suy ra \( a_{n+1}^2 - a_n a_{n+2} = b^2 - 6ab + a^2 \), hay

\[ a_{n+1}^2 - a_n (6a_{n+1} - a_n) = b^2 - 6ab + a^2, \] \[ (a_{n+1} - a_n)^2 = 4a_n a_{n+1} + b^2 - 6ab + a^2. \]

Giả sử rằng số \( p \) nguyên dương thỏa mãn yêu cầu bài toán, tức là

\[ (a_{n+1} - a_n)^2 + p - (b^2 - 6ab + a^2) \]

là số chính phương với mọi \( n \). Không khó để thấy rằng dãy các số \( (a_{n+1} - a_n) \) là dãy số nguyên dương tăng, tiến đến vô cùng. Do vậy, để thỏa mãn yêu cầu bài toán thì ta phải có \( p = b^2 - 6ab + a^2 \).

Ở chiều ngược lại, với bất kì số \( p \) nguyên dương có dạng \( b^2 - 6ab + a^2 \), ta chọn \( a_1 = a, \quad a_2 = b \), và thu được

\[ p + 4a_n a_{n+1} = (a_{n+1} - a_n)^2 \quad \forall n \in \mathbb{N}. \]

Bài toán (VMO 2018-2019)

Cho dãy số nguyên dương \( (x_n) \) thỏa mãn \( 0 \leq x_0 < x_1 \leq 100 \) và

\[ x_{n+2} = 7x_{n+1} - x_n + 280, \quad \forall n \geq 0. \]

a) Chứng minh rằng nếu \( x_0 = 2, x_1 = 3 \) thì với mỗi số nguyên dương \( n \), tổng các ước nguyên dương của \( x_n x_{n+1} + x_{n+1} x_{n+2} + x_{n+2} x_{n+3} + 2018 \) thì chia hết cho 24.

b) Tìm tất cả các cặp số \( (x_0, x_1) \) để số \( x_n x_{n+1} + 2019 \) là số chính phương với vô số số \( n \).

Lời giải.

a) Bổ đề. Số \( n \in \mathbb{Z}^+ \) thỏa mãn \( 24 \mid n + 1 \) thì tổng các ước dương \( \sigma(n) \) của nó chia hết cho 24.

Thật vậy, nếu \( d \) là ước của \( n \) thì \( \frac{n}{d} \) cũng là ước của \( n \). Do \( n \equiv 2 \ (\text{mod}\ 3) \) nên nó không thể là số chính phương, chứng tỏ các ước của nó có thể chia cặp với dạng \( d + \frac{n}{d} = \frac{d^2 + n}{d} \).

Chú ý rằng \( n \equiv 2 \ (\text{mod}\ 3) \) và \( d^2 \equiv 1 \ (\text{mod}\ 3) \) nên tổng trên chia hết cho 3.

Mặt khác, \( n \equiv 7 \ (\text{mod}\ 8) \) và \( d \equiv 1, 3, 5, 7 \ (\text{mod}\ 8) \), suy ra \( d^2 \equiv 1 \ (\text{mod}\ 8) \) nên tổng trên cũng chia hết cho 8. Vì \( (3, 8) = 1 \) nên tổng trên chia hết cho 24, bố đề được chứng minh.

Trở lại bài toán,

Đặt \( y_n = x_n x_{n+1} + x_{n+1} x_{n+2} + x_{n+2} x_{n+3} \), ta cần chứng minh rằng \( \sigma(y_n + 2018) \) chia hết cho 24. Ta cũng có \( 2018 \equiv 2 \ (\text{mod}\ 24) \) nên theo bố đề, ta cần có \( y_n \equiv -3 \ (\text{mod}\ 24) \).

Xét chu kỳ của số dư khi chia cho 3 của dãy thông qua nhận xét \( x_{n+2} \equiv x_{n+1} - x_n + 1 \ (\text{mod}\ 3) \) ta có \( 2, 0, 2, 0, 2, 0, \ldots \) dãy số dư này tuần hoàn theo chu kỳ 2 và

\[ y_n \equiv 0 \cdot 2 + 2 \cdot 0 + 0 \cdot 2 = 0 \ (\text{mod}\ 3). \]

Lại xét chu kỳ của số dư khi chia cho 8 của dãy thông qua nhận xét \( x_{n+2} \equiv -x_{n+1} - x_n \ (\text{mod}\ 8) \) ta có \( 2, 3, 3, 2, 3, 3, 2, 3, 3, \ldots \) nghĩa là dãy này tuần hoàn với chu kỳ 3 và

\[ y_n \equiv 2 \cdot 3 + 3 \cdot 3 + 3 \cdot 2 = 5 \ (\text{mod}\ 8). \]

Suy ra \( y_n + 3 \) vừa chia hết cho 3, vừa chia hết cho 8 nên \( y_n \equiv -3 \ (\text{mod}\ 24) \). Ta có đpcm.

b) Theo bổ đề đã biết, ta thấy rằng tồn tại \( C \in \mathbb{Z} \) sao cho \( x_{n+1}^2 - x_n x_{n+2} - 280 x_{n+1} = C \). Từ đó suy ra

\[ x_{n+1}^2 - x_n (7 x_{n+1} - x_n + 280) - 280 x_{n+1} = C \] \[ \Leftrightarrow x_{n+1}^2 + x_n^2 - 7 x_{n+1} x_n - 280 (x_{n+1} + x_n) = C \] \[ \Leftrightarrow (x_{n+1} + x_n - 140)^2 = 9 (x_{n+1} x_n + 2019) - 9 \cdot 2019 + C + 140^2 \] \[ \Leftrightarrow u_n^2 = v_n^2 + C + 1429 \]

trong đó, \( u_n = x_{n+1} + x_n - 140 \), \( v_n = 3 \sqrt{x_{n+1} x_n + 2019} \) với mọi \( n \geq 0 \).

Vì dãy \( (x_n) \) tăng mà các giá trị đều là số nguyên nên dãy này không bị chặn, do đó, \( (u_n) \) tăng và không bị chặn. Đồng thời, nếu \( x_n x_{n+1} + 2019 \) là số chính phương thì \( v_n \in \mathbb{Z}^+ \).

Do đó, \( u_n + v_n \mid C + 1429 \) với vô hạn giá trị \( n \). Rõ ràng điều này chỉ xảy ra khi \( C + 1429 = 0 \). Vì thế nên ta có đẳng thức

\[ (x_{n+1} + x_n - 140)^2 = 9 (x_{n+1} x_n + 2019) \]

với mọi số tự nhiên \( n \).

Ta có \( (x_0 + x_{1} - 140)^2 \geq 2019 \cdot 9 > 44^2 \cdot 3^2 = 132^2 \) nên \( |140 - x_0 - x_1| \geq 133 \) mà \( 0 \leq x_0 < x_1 < 101 \) nên \( 140 - (x_0 + x_1) \geq 133 \), tức là \( x_0 + x_1 \leq 7 \). Ta cũng có

\[ C = x_1^2 + x_0^2 - 7 x_1 x_0 - 280 (x_1 + x_0) = -1429. \]

Để ý rằng \( x_1^2 + x_0^2 \leq 49 \) nên \( -1429 = C < 49 - 280 (x_1 + x_0) \), kéo theo \( x_0 + x_1 \geq 5 \).

Với \( x_1 + x_0 = 7 \) thì \( x_1^2 + x_0^2 - 7 x_1 x_0 = 531 \) và với \( x_1 + x_0 = 6 \) thì \( x_1^2 + x_0^2 - 7 x_1 x_0 = 251 \), dễ thấy đều không thỏa. Do đó \( x_0 + x_1 = 5 \), kéo theo \( x_0 x_1 = 6 \) nên dễ thấy \( x_0 = 2 \), \( x_1 = 3 \).

Vậy cặp giá trị cần tìm là \( (x_0; x_1) = (2; 3) \).

Bài toán

Cho dãy số \( (F_n) \) xác định bởi \( F_1 = F_2=1 \) và

\[ F_{n+2} = F_{n+1} + F_n, \quad \forall n. \] và dãy số \( (L_n) \) xác định bởi \( L_1 = 1, L_2=3 \) và \[ L_{n+2} = L_{n+1} + L_n, \quad \forall n. \] Chứng minh rằng :

a) \((F_n,F_{n+1})=1\) và \((L_n,L_{n+1})=1\) với mọi \(n\), trong đó \((a,b)\) là ước chung lớn nhất của \(a\) và \(b\).

b)\(F_n|F_{nk}\).

c) \((F_m,F_n)=F_{(m,n)}\)

d) \(F_m|F_n\) khi và chỉ khi \(m|n\)

e) \(L_m|F_n\) khi và chỉ khi \(n=2km\)

f) \(L_m|L_n\) khi và chỉ khi \(n=(2k+1)m\)

g) Gọi \(R\) là số dư của \(F_n\) khi chia cho \(F_m\) (\(n>m\)). Chứng minh rằng tồn tại \(s\) sao cho \(R=F_s\) hoặc \(F_m-R=F_s\).

h) Gọi \(R\) là số dư của \(L_n\) khi chia cho \(L_m\) (\(n>m\)). Chứng minh rằng \(R=0\) hoặc tồn tại \(s\) sao cho \(R=L_s\) hoặc \(L_m-R=L_s\).

Lời giải

a) Dễ thấy rằng hai số Fibonacci liên tiếp không có ước chung lớn hơn 1. Nếu \( F_{n+2} \) và \( F_{n+1} \) có một ước chung \( d \), thì \( F_n = F_{n+2} - F_{n+1} \) cũng sẽ chia hết cho \( d \). Do đó, ta có thể tiếp tục xuống đến \( F_2 = 1 \) chia hết cho \(d\). Vì \( d \) là số nguyên dương, nên \( d \) chỉ có thể là 1. Lập luận tương tự cũng áp dụng cho các số Lucas.

b) \[ \begin{aligned} F_{nk} &= \frac{\alpha^{nk} - \beta^{nk}}{\alpha - \beta} \\ &= \frac{\alpha^k - \beta^k}{\alpha - \beta} (\alpha^{(n-1)k} + \alpha^{(n-2)k}\beta^k \\ &\qquad + \alpha^{(n-3)k}\beta^{2k} + \dots + \alpha^k\beta^{(n-2)k} + \beta^{(n-1)k}) \end{aligned} \]

Trong dấu ngoặc bên phải, số hạng đầu tiên và số hạng cuối cùng có thể được ghép cặp để tạo thành một số Lucas:

\[ \alpha^{(n-1)k} + \beta^{(n-1)k} = L_{(n-1)k} \]

Các số hạng thứ hai và áp chót có thể được ghép cặp để tạo thành tích của \((-1)^k\) và một số Lucas:

\[ \begin{aligned} \alpha^{(n-2)k}\beta^k + \alpha^k\beta^{(n-2)k} &= \alpha^k\beta^k(\alpha^{(n-3)k} + \beta^{(n-3)k})\\ &= (\alpha\beta)^k L_{(n-3)k} = (-1)^k L_{(n-3)k} \end{aligned} \]

Và cứ tiếp tục như vậy. Lưu ý rằng số lượng số hạng trong dấu ngoặc bên phải là \( n \). Nếu \( n \) là số chẵn, thì các số hạng sẽ kết hợp thành từng cặp đối xứng để tạo thành các số Lucas, rõ ràng là một số nguyên.

Nếu \( n \) là số lẻ, thì các số hạng vẫn ghép cặp đối xứng ngoại trừ số hạng ở giữa, có dạng \( (\alpha\beta)^{(n-1)k/2} \), rõ ràng là một số nguyên. Một lần nữa, biểu thức trong dấu ngoặc bên phải là số nguyên. Do đó ta có điều phải chứng minh.

d) Đây chỉ là hệ quả của câu c.

Bài toán (VMO 2017-2018)

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, \quad \forall n \geq 0. \]

a) 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ẻ.

b) Tìm tất cả 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.

a) Ta chứng minh được \( x_n = \alpha^n + \beta^n \) với mọi \( n \in \mathbb{N}^* \), trong đó \( \alpha < 0 < \beta \) là hai nghiệm của phương trình đặc trưng \( \lambda^2 - \lambda - 1 = 0 \).

Giả sử \( x_n \) là số nguyên tố với \( n \) là số nguyên dương có ước nguyên tố lẻ. Khi đó, \( n \) có dạng \( pq \) với \( p \) là số nguyên tố lẻ và \( q \) là số tự nhiên lớn hơn 1. Ta có

\[ \begin{align*} x_{pq} &= \alpha^{pq} + \beta^{pq} \\ &= (\alpha^q + \beta^q) \left( \alpha^{q(p-1)} - \alpha^{q(p-2)} \beta^q + \alpha^{q(p-3)} \beta^{2q} - \cdots - \alpha^q \beta^{q(p-2)} + \beta^{q(p-1)} \right) \\ &= (\alpha^q + \beta^q) \left[ (\alpha^{q(p-1)} + \beta^{q(p-1)}) + \cdots + (-1)^{\frac{(q+1)(p+1)}{2}} (\alpha^{2q} + \beta^{2q}) + (-1)^{\frac{(q+1)(p-1)}{2}} \right] \\ &= x_q \left( x_{q(p-1)} + \cdots + (-1)^{\frac{(q+1)(p+1)}{2}} x_{2q} + (-1)^{\frac{(q+1)(p-1)}{2}} \right) \end{align*} \]

nên \( x_{q} \mid x_{pq} \). Mặt khác, dễ thấy dãy \( (x_n) \) tăng ngặt kể từ \( n = 1 \) nên \( x_q > x_1 = 1 \). Do đó, \( x_{pq} \) là hợp số, mâu thuẫn. Vậy, với \( n \geq 1 \), để \( 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) Xét các trường hợp sau:

• Trường hợp 1: \( m = 0 \). Xét trong modulo 2, ta có \( x_0 = 0 \), \( x_1 = 1 \), \( x_2 = 1 \), \( x_3 = 0 \), \( x_4 = 1 \), \( x_5 = 1 \), \( x_6 = 0 \), \(\ldots\) Do đó, \( x_n \) chẵn với mọi \( n \) chia hết cho 3 và lẻ trong các trường hợp còn lại. Từ đây suy ra, để \( x_n \) chia hết cho \( x_0 \), ta phải có \( n \) chia hết cho 3. Cặp số \( (m, n) \) thỏa mãn trong trường hợp này là \( (0, 3k) \) với \( k \in \mathbb{N} \).

• Trường hợp 2: \( m = 1 \). Dễ thấy \( (m, n) = (1, k) \) với \( k \in \mathbb{N} \).

• Trường hợp 3: \( m > 1 \). Với mọi \( k \geq \ell \geq 0 \), ta có

  \[ (\alpha^k + \beta^k)(\alpha^\ell + \beta^\ell) - (\alpha^{k+\ell} + \beta^{k+\ell}) = (\alpha \beta)^\ell (\alpha^{k-\ell} + \beta^{k-\ell}) = (-1)^\ell (\alpha^{k-\ell} + \beta^{k-\ell}). \]

  Do đó

  \[ x_{k+\ell} = x_k x_\ell - (-1)^\ell x_{k-\ell}. \quad (1) \]

  Nói cách khác, với mọi \( k \geq 2\ell \geq 0 \), ta có

  \[ x_k = x_{k-\ell} x_\ell - (-1)^\ell x_{k-2\ell}. \]

  Do đó \( x_k \) chia hết cho \( x_\ell \) khi và chỉ khi \( x_{k-2\ell} \) chia hết cho \( x_\ell \), \( x_{k-2\ell} \) chia hết cho \( x_\ell \) khi và chỉ khi \( x_{k-4\ell} \) chia hết cho \( x_\ell \) (nếu \( k \geq 4\ell \)), \(\ldots\) Một cách tổng quát, ta có \( x_k \) chia hết cho \( x_\ell \) khi và chỉ khi \( x_{k-2\ell t} \) chia hết cho \( x_\ell \) (nếu \( k \geq 2\ell t \), \( t \in \mathbb{N} \)). (2)

  Bây giờ, do \( x_n \) chia hết cho \( x_m \) nên \( x_n \geq x_m \geq 3 \), suy ra \( n \geq m > 1 \). Đặt \( n = q m + r \) với \( q \in \mathbb{N}^* \), \( r \in \mathbb{N} \), \( 0 \leq r \leq m - 1 \). Xét các trường hợp sau:

  • Trường hợp 3.1: \( q \) chẵn. Theo nhận xét (2), ta có \( x_n \) chia hết cho \( x_m \) khi và chỉ khi \( x_r \) chia hết cho \( x_m \). Suy ra

    \[ x_r \geq x_m. \]

    Nếu \( r \geq 1 \) thì từ bất đẳng thức trên, ta suy ra \( r \geq m \) (do \( \{x_n\} \) tăng ngặt với mọi \( n \geq 1 \)), mâu thuẫn. Do đó \( r = 0 \), tuy nhiên điều này cũng mâu thuẫn vì

    \[ x_m \geq x_2 = 3 > x_0 = x_r. \]

  • Trường hợp 3.2: \( q \) lẻ. Theo nhận xét (2), ta có \( x_n \) chia hết cho \( x_m \) khi và chỉ khi \( x_{m+r} \) chia hết cho \( x_m \). Mặt khác, theo (2), ta lại có

    \[ x_{m+r} = x_m x_r - (-1)^r x_{m-r} \]

    nên \( x_n \) chia hết cho \( x_m \) khi và chỉ khi \( x_{m-r} \) chia hết cho \( x_m \). Nếu \( 0 < r < m \), ta có \( 1 \leq m - r \) nên \( x_{m-r} < x_m \), mâu thuẫn. Do đó, \( r = 0 \) và giá trị này thỏa mãn. Suy ra, trong trường hợp này, cặp số \( (m, n) \) thỏa mãn yêu cầu là \( (m, (2k+1)m) \) với \( k \in \mathbb{N} \).

    Tóm lại, các cặp số cần tìm là \( (0, 3k), (1, k) \) và \( (m, (2k+1)m) \) với \( m, k \in \mathbb{N}, m > 1 \).

  Bài toán (IMO Shortlist 1988)

  Cho dãy số nguyên \( (a_n) \) xác định bởi :

  \[ a_0 = 0, \quad a_1 = 1, \quad a_{n+2} = 2a_{n+1} + a_n. \]

  Chứng minh rằng \( 2^k \mid a_n \) khi và chỉ khi \( 2^k \mid n \).

  Lời giải

  Bổ đề : Cho dãy số \( (x_n) \) xác định bởi \( x_1 = a, x_2 = b \) và :

  \[ x_{n+2} = b x_{n+1} + a x_n. \]

  Khi đó với \( m \) nguyên dương bất kỳ, ta có :

  \[ x_{m+n} = x_n x_{m+1} + x_{n-1} x_m \quad (*) \]

  Chứng minh bổ đề

  Ta chứng minh bằng quy nạp theo \( m \), với \( m = 1 \) thì hiển nhiên. Giả sử (*) đúng với \( m \) và \( m - 1 \). Xét với \( m + 1 \):

  \[ \begin{align*} x_{m+n+1} &= b x_{m+n} + a x_{m+n-1} \\ &= b(x_n x_{m+1} + x_{n-1} x_m) + a(x_n x_m + x_{n-1} x_{m-1}) \\ &= x_n (b x_{m+1} + a x_m) + x_{n-1} (b x_m + a x_{m-1}) \\ &= x_n x_{m+2} + x_{n-1} x_{m+1} \end{align*} \]

  Quy nạp hoàn tất, như vậy ta có đẳng thức (*).

  ---

  Kết quả này là một kết quả quan trọng được dùng cho nhiều bài toán.

  Trở lại bài toán

  Ta chọn \( m = n \) trong (*) thì ta được :

  \[ x_{2n} = x_n (x_{n-1} + x_{n+1}) = 2x_n (x_n + x_{n-1}) \quad (\ast\ast) \]

  Bằng quy nạp ta chứng minh được \( a_{2n+1} \) lẻ và \( a_{2n} \) chẵn. Như vậy \( x_n + x_{n-1} \) lẻ.

  Nếu \( 2^k \mid a_n \). Đặt \( n = 2^m t \), với \( t \) lẻ. Sử dụng (*) ta được :

  \[ 2^k \mid a_n = a_{2^m t} \Rightarrow 2^{k-1} \mid a_{2^{m-1} t} \Rightarrow 2^{k-2} \mid a_{2^{m-2} t} \]

  Nếu \( k > m \) thì cứ tiếp tục quá trình này, ta được \( 2^{k-m} \mid a_t \) và điều này vô lí vì \( a_t \) lẻ (do \( t \) lẻ).

  Vậy phải có \( k \leq m \), suy ra \( 2^k \mid 2^m t = n \).

  Nếu \( 2^k \mid n \). Đặt \( n = 2^k t \) và cũng sử dụng (**) ta có :

  \[ 2^0 \mid a_t \Rightarrow 2^1 \mid a_{2t} \Rightarrow 2^2 \mid a_{2^2 t} \Rightarrow \ldots \Rightarrow 2^k \mid a_{2^k t} = a_n \]

  Bài toán hoàn tất.

  Link