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" <achava@hotmail.com> wrote:

> Grok Ltd wrote:
> 
> > Does anybody out there know how to prove this?
> > hcf(u_p, n) = 1, for all n<p, (p prime)
> > 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" 
<james@jwanless.freeserve.co.uk> 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<p
> (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<q                                [since p,q both odd]
> 
> [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