# Proving that there are infinitely-many prime numbers that are not Fibonacci numbers

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?

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

## 1 Answer

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.

• 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). – Lorem Ipsum Jan 21 at 0:14
• This is similar to the answer given, but requires a (much) easier case of Dirichlet's Theorem. – Lorem Ipsum Jan 21 at 0:14