Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

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/

Associated Topics:
High School Fibonacci Sequence/Golden Ratio

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search