From: steiner@math.bgsu.edu (ray steiner) Subject: Re: Fibonacci Sequence Question Please Date: Thu, 16 Sep 1999 16:24:18 -0500 Newsgroups: sci.math Keywords: divisors of Fibonacci numbers In article <37DFE1D5.5F1C083B@hotmail.com>, "Achava Nakhash, the Loving Snake" wrote: > Grok Ltd wrote: > > > Does anybody out there know how to prove this? > > hcf(u_p, n) = 1, for all n > James > Here's the proof I promised a while back: Definition. Let F_n be the nth Fibonacci number. A divisor d of F_n is called primitive if d | F_n but d | F_i for all i, i < n. Now let p and q be odd primes, with neither equal to 5. We require the following facts about Fibonacci numbers, which can be found in elementary works on the subject. 1). (F_m, F_n)= F_(m,n). (Proved by Euclid's algorithm.) 2). If p = 5k \pm 1 then p | F_{p-1} and F_p = 1(mod p). If p= 5k \pm 2 then p | F{p+1} and F_p = -1(mod p). . 3). If p is a primitive divisor of F_n and p | a_i, then a_n | a_i. Theorem: Every prime divisor of F_p is primitive. Proof: Suppose q | F_p. and n < p, then (n,p)=1, since p is prime. Now (F_n, F_p)= F_(n,p) = F_1=1. Thus q cannot divide F_n. So, q is primitive. Corollary: If q | F_p then q > p. Proof. First, let q= 5k \pm 1. Then q | F_{q-1}. By 3). and the Theorem, we get F_p | F_{q-1}, so p | q-1. This yields q >= p+1, and, since q .ne. 2, q > p. Now let q= 5k \pm 2. Then q | F_{q+1}. As before, F_p | F_{q+1}. Thus p | q+1, so q+1 >= p. Since q is odd, q+1 > p. But p .ne. q, by 2). so, q > p. This proves the result. Challenge: Extend the result of the corollary. Prove that, in fact, q >= 2p - 1. Open question: Can F_p ever contain a square factor? Despite a lot of work on this question, it is still wide open! Regards, Ray Steiner -- steiner@math.bgsu.edu ============================================================================== From: steiner@math.bgsu.edu (ray steiner) Subject: Re: Fibonacci Sequence Question Please Date: Fri, 17 Sep 1999 14:01:02 -0500 Newsgroups: sci.math In article <7rto3h$cbh$1@news5.svr.pol.co.uk>, "James Wanless" wrote: > Thanks for this, Ray. > The current state of play is (as I summarise/surmise): > > > > p,q odd primes <>5 > > Suppose q|F_p, with n

(F_n,F_p)=F_(n,p)=F_1=1 [by Lemma 1] > => q\|F_n, i.e q primitive > > q|F_(q+/-1) [by Lemma 2] > => F_p|F_(q+/-1) [by Lemma 3, q primitive] > => p|q+/-1 [by Lemma 4] > => p > [challenge: actually, since p odd, p|(q+/-1)/2 too, so q>=2p-1] > > > > Lemma 1 (I have proof in my book - OK) > (F_m,F_n)=F_(m,n) > > Lemma 2 (stated w/o proof, also, in my book - please supply ref for proof?) > q<>5, q|F_(q-1) or q|F_(q+1) > > Lemma 3 (please supply ref for (more general?) proof?) > If q is primitive divisor of F_p and q|F_n, then F_p|F_n Sorry, this should read as follows: If p is a primitive divisor of F_n and p | F_i then F_n | F_i . > > Lemma 4 (I have proof in my book - OK) > F_p|F_n => p|n Here is the proof of Lemma 3. I will send the proof of Lemma 2 when I have more time. If p is a primitive divisor of F_n then those F_i with indices nk and only those are divisible by p. (This should be in your book.) Thus i= nk. But n | nk, so F_n | F_i . Proof of Lemma 2 to follow soon! Regards, Ray Steiner -- steiner@math.bgsu.edu