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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum