fibonacciprime

Fibonacci Prime

There are an infinite number of primes among the Fibonacci sequence numbers Un.

Proof:

hcf (Up, n) = 1, for all n<p [by Lemma 1]

let p->99999… [Euclid]

=> Up prime

=> there exist an infinite number of prime Up

LEMMA 1

Any divisor of Up is greater than p [p odd prime <>5]

Proof:

q | U(q+/-1) [q odd prime <>5][by Lemma 2]

=> Up | U(q+/-1) [by Lemmas 3 & 4]

=> p | q+/-1

=> p<q [since p,q both odd]

LEMMA 2

q prime <>5 => q | U(q-1) or q | U(q+1)

LEMMA 3

q is a primitive divisor of Up

Proof:

Suppose q | Up, with n<p [p prime]

hcf (Un,Up) = U(hcf (n,p)) = U1 = 1

=> Un<>0 mod q, i.e. q primitive divisor of Up

LEMMA 4

If q is a primitive divisor of Un and q | Um, then Un | Um

Proof:

If q is a primitive divisor of Un, then q | Unj only

n | nj => Un | Unj