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