2
$\begingroup$

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?

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

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.

$\endgroup$
  • $\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 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 at 0:14

Your Answer

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