|
Consider the remainders of consecutive pairs of Fibonacci numbers when divided by m. Since there are m remainders, there are m^2 distinct pairs of remainders. Hence, for some i<j, the remainders of the pair (F(i),F(i+1)) and the the remainders of the pair (F(j),F(j+1)) must be the same pair. That is, the remainders of F(i) and F(j) are the same and the remainders of F(i+1) and F(j+1) are the same.
But then the remainders of F(i-1) and F(j-1) are the same because
F(i-1)=F(i+1)-F(i) and
F(j-1)=F(j+1)-F(j),
have the same remainder when divided by m. Continuing, F(i-2) has the same remainder as F(j-2), etc. Thus 0=F(0)=F(i-i) has the same remainder as F(j-i); and so F(j-i) is divisible by m.
(According to the unlimited precision software GAP, 2001 divides the 860th term of the Fibonacci sequence but does not divide any earlier term after the first term.) |
