Fibonacci numbers $\{F_n\}_n\in\mathbb{N}$ are defined by the sequence $F_{n+2}=F_{n+1}+F_{n}$, $F_1=F_2=1$. Now prove that there are infinitely many prime numbers which are not Fibonacci numbers.

I tried very much and tried to get a proof by contradiction, but failed. I assumed the negation, but it takes me nowhere.

I assumed that there is a prime number which is a Fibonacci number and the next prime is also a Fibonacci number. Hence, as there is at least one prime between $n$ and $2n$, then $2n$ will have a Fibonacci number form, which can be hence expressed as a prime. But I am not sure what to do next. Is my assumption correct after all?

  • $\begingroup$ Why the negative reactions ? The question is clear and an effort is shown. $\endgroup$ – Peter Jan 20 '19 at 14:48
  • $\begingroup$ yes that is what i am thinking $\endgroup$ – user636268 Jan 20 '19 at 14:52

Analyzing mod $11$, you can show that no fibonacci-number has the form $11k+4$, but infinite many primes have that form because of Dirichlet's theorem.

  • 1
    $\begingroup$ One can easily prove (by induction or otherwise) the identities $$F_{2n} = (F_{n-1} + F_{n+1}) F_n,$$ $$F_{2n-1} = F^2_n + F^2_{n-1}.$$ From the first identity, $F_{2n}$ is never prime for $n > 2$. From the second identity, if $F_{2n-1} = p$ is prime, then it is a sum of squares, which forces $p = 2$ or $p \equiv 1 \bmod 4$. So the only prime $F_n$ are either $F_3 = 2$, $F_4 = 3$, or are $1 \bmod 4$. But there are infinitely many primes of the form $3 \bmod 4$ (take $4$ times the product of all such primes and then subtract one; this number has a new prime factor of this form). $\endgroup$ – Lorem Ipsum Jan 21 '19 at 0:14
  • $\begingroup$ This is similar to the answer given, but requires a (much) easier case of Dirichlet's Theorem. $\endgroup$ – Lorem Ipsum Jan 21 '19 at 0:14

Let us assume to the contrary that only finitely many primes are not Fibonacci numbers. Suppose the largest of them is $p_{k}$. Then for every n>k, $p_{n}$ must be some Fibonacci number. Now we know, $F_{2n+1}= F_{2n}+F_{2n-1}> F_{2n-1}+F_{2n-1}=2F_{2n-1}$ or, $F_{2n+1}>2F_{2n-1}$

Now we know there exists at least 1 prime between n and 2n. So, there must exist a prime between $F_{2n-1}$ and $2F_{2n-1}$. Therefore, there should exist a prime between $F_{2n+1}$ and $F_{2n-1}$ .

Now, suppose the prime be $p_{n}$ where n>k. So, according to our assumption $p_{n}$ is a fibonacci number. And $p_{n}$ lies between $F_{2n-1}$ and $F_{2n+1}$. So, $p_{n}$ must be $F_{2n}$. But for any n in N, $F_{2n} = (F_{n-1} + F_{n+1})F_{n}$ . Hence, $F_{2n}$ cannot be a prime. So, we reach a contradiction. [Hence, proved]


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy