p divides Fibonacci(A*p^2+B)-F(A+B) ?

[John Conway]

On Wed, 10 Sep 2003, benoit wrote:

> Let F(n) denotes the n-th Fibonacci number. It seems that if p is a 
> prime different from 5 :
> 
> p divides F(A*p^2+B)-F(A+B) for any (A,B) in N^2.

    In other words, if  M  is congruent to  N,  modulo  p^2 - 1,
then  F(M)  is congruent to  F(N)  modulo  p.  Yes, that's true,
and can be proved as follows.

   We have  F(N) = (tau^n - sigma^n)/(tau - sigma),  where  tau  and
sigma  are  (1 +- root5)/2.  Now except in the case  p = 5, we can
read this modulo  p,  but sometimes only at the cost of enlarging
the field of integers modulo p to the finite field of order  p^2.
Since the multiplicative group of that field has order  p^2 - 1,
the values of  tau^n  and  sigma^n  won't be altered when we 
increase  n  by a multiple of  p^2 - 1,  and we're done.

   [What happens when  p = 5  is that the denominator - which equals  
root5  -  is one we can't divide by,  modulo  5.]

       John Conway