From: rchapman@mpce.mq.edu.au
Subject: Re: Yet another Fibonacci question
Date: Wed, 27 Jan 1999 04:13:49 GMT
Newsgroups: sci.math
Keywords: Fibonacci mod p

In article <78kqdb$sot@alpha5.mth.uea.ac.uk>,
  h720@alpha5.mth.uea.ac.uk (T.Ward) wrote:
>
> Hello - apologies if this is a very standard fact.
>
> Does anyone know a reference for the following
> congruences in the Fibonacci numbers (F_1=1,F_2=1,F_3=2,...):
>
> for prime p,
>
> F_{p-1} mod p  is  0 or 1  unless p is <= 5.
>
> Moreover, when F_{p-1} is 0 mod p, F_{p-2} is 1 mod p.
>
> Probably not hard, but I'd like to know the right
> place to look.
>

If you really want a reference, this is not going to be of much use, but the
result is easily proved. Note that F_n = (a^n - b^n)/(a - b) where a and b
are the roots of the equation x^2 - x - 1 = 0. If p is a prime other than 5,
then the roots of this equation are distinct in an extension of GF(p) and
this formula holds modulo p as well. If a and b lie in GF(p) (by quadratic
reciprocity if p = 1 or 4 mod 5) then in GF(p) we have a^p = a and b^p = p so
that F_p = 1 mod p. On the other hand if a and b are not in GF(p) they are
conjugate in GF(p^2) so that a^p = b and b^p = a. Then F_p = -1 (mod p) for
these primes (where p = 2 or 3 mod 5). For p = 1 or 4 mod 5 we have a^{p-1} =
b^{p-1} = 1 in GF(p) and so F_{p-1} = 0 mod p (and so F_{p+1} = 1 mod p). For
p = 2 or 3 mod 5 then a^{p+1} = ab = b^{p+1} in GF(p^2) and so F_{p+1} = 0
mod p (and so F_{p-1} = 1 mod p).

Robin Chapman                           + "Going to the chemist in
Department of Mathematics, DICS         -  Australia can be more
Macquarie University                    +  exciting than going to
NSW 2109, Australia                     -  a nightclub in Wales."
rchapman@mpce.mq.edu.au                 +   Howard Jacobson,
http://www.maths.ex.ac.uk/~rjc/rjc.html -     In the Land of Oz

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own