Tài liệu Lời giải và bình luận đề thi các tỉnh, các trường đại học năm học 2009-2010

Cách 2. Ta chứng minh mệnh đề tổng quát: Với mọi số nguyên dương N, tồn tại vô
số số hạng của dãy số Fibonacci chia hết cho N.
Để thực hiện điều này, ta bổ sung thêm số hạng F0 = 0 cho dãy Fibonacci. Chú
ý là ta vẫn có hệ thức Fn+1 = Fn + Fnư1 với mọi n = 0, 1, 2, . Gọi ri là số dư
trong phép chia Fi cho N. Xét N 2 + 1 cặp số dư (r0 , r1 ), (r1 , r2 ), . , (rN , rN+1 ).
Do 0 ≤ ri ≤ N ư 1 nên chỉ có N 2 cặp giá trị (ri , ri+1 ) khác nhau. Theo nguyên lý
Dirichlet, tồn tại cặp chỉ số i < j sao cho (ri , ri+1 ) ≡ (r j , r j+1 ). Từ đây, do rkư1
chính là số dư trong phép chia rk+1 ư rk cho N nên ta suy ra riư1 = r jư1 , riư2 = r jư2 ,
. , r0 = r jưi . Suy ra dãy số dư tuần hoàn với chu kỳ j ư i. Vì r0 = 0 nên rk( jưi) = 0
với mọi k = 1, 2, . và ta có rk( jưi) chia hết cho N với mọi k = 1, 2, . (đpcm).