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