Primes in Fibonacci

Date: 07/11/99 at 18:27:44
From: Carly White
Subject: Primes in Fibonacci

Dear Dr Math,

Is there any pattern with prime numbers in the Fibonacci sequence?

Date: 07/12/99 at 10:57:24
From: Doctor Floor
Subject: Re: Primes in Fibonacci

Dear Carly,

Thanks for your question!

This is a very interesting question indeed. As far as I know, it 
is not known whether there are infinitely many prime numbers in 
Fibonacci's sequence or not.

There is some pattern however, in the sense that we know that if a 
Fibonacci number F(n) is prime (here we take F(1) = 1, F(2) = 1, 
F(3) = 2, etc.) and n > 4, then n is prime too. Or, in other words,
when n > 4 is a composite number, then F(n) is a composite number too.

A proof of this is not too difficult. When n is even, so it can be 
written as n = 2m, it follows from the fact that F(2m) = F(m)*L(m), 
where L(m) is the mth Lucas number. You can find a proof of this in 
the Dr. Math archives:

  http://mathforum.org/dr.math/problems/ng8.24.98.html   

Since n > 4, we see that m > 2, and thus L(m) and L(n) are both 
greater than 1, and F(2m) must be composite.

To prove a more general statement we will use the terminology and
formulae of the message in the Dr. Math archives I pointed you to.
So:

   P = (1+SQRT(5))/2
   Q = (1-SQRT(5))/2
   F(n) = (P^n - Q^n)/SQRT(5)
   L(n) = P^n + Q^n

Now let n = p*q with p>2 and q>1 (in this way we describe all existing
composite numbers greater than 4). We have:

  F(n) = F(p*q) = [P^(p*q) - Q^(p*q)]/SQRT(5) =
  [(P^p)^q - (Q^p)^q]/SQRT(5) =
  (P^p - Q^p)/SQRT(5) * 
    [(P^p)^(q-1) + Q^p*(P^p)^(q-2) + ... + (Q^p)^(q-1) ] =  (*)
  F(p) * [(P^p)^(q-1) + Q^p*(P^p)^(q-2) + ... + (Q^p)^(q-1)]

(*): This is a special case of: 
x^n-y^n = (x-y)[x^(n-1) + y*x^(n-2) + y^2*x^(n-3) + ... + y^(n-2)*x +
y^(n-1)]

Since F(p) > 1, and clearly F(n) > F(p), we can now see that F(n) is a 
composite number when
[(P^p)^(q-1) + Q^p*(P^p)^(q-2) + ... + (Q^p)^(q-1) ]
is an integer. This can be shown using that  L(n) = P^n + Q^n is an
integer, and P^n*Q^n = (P*Q)^n = (-1)^n. I will not go over writing 
this all out exactly, but I think you will understand how to prove it 
when I give as an example how to show that F(15) is composite:

  F(15) = F(5*3) = [P^15 - Q^15]/SQRT(5) =
  [P^3 - Q^3]/SQRT(5)*(P^12 + P^9*Q^3 + P^6*Q^6 + P^3*Q^9 + Q^12) =
  F(3) * [P^12 + Q^12 + (P*Q)^3*(P^6 + Q^6) + (P*Q)^6] =
  F(3) * [ L(12) - L(6) + 1]

It is clear here that L(12) - L(6) + 1 is an integer, and thus F(15) 
is composite.

And our conclusion stands: when F(n) is prime and n > 4, then n itself
must be prime.

If you have a math question again, or if you need more help on this,
don't hesitate to write us back.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/