16
$\begingroup$

In[11]:= Select[Table[Fibonacci[n], {n, 1, 10000}], PrimeQ[# - 1] &]

Out[11]= {3, 8}

Edit: Fibonacci[n]-1 is always composite for n>6. why? $\sum\limits_{i = 0}^n {{F_i}} = {F_{n + 2}} - 1$

In[16]:= Select[Table[Fibonacci[n], {n, 1, 10000}], PrimeQ[# + 1] &]

Out[16]= {1, 1, 2}

Fibonacci[n]+1 is always composite for n>3. why?

  • 0
    (This is not meant seriously) The probability that an odd number of the form $a_n:=$ Fib$(n)\pm 1$ is prime is about ${\rho\over n}$ for a certain constant $\rho$. It follows that you can expect an infinity of primes among the $a_n$. Note that Fib$[84]-1 = 370248451 * 433494437$, a near-miss.2011-01-09

2 Answers 2

18

mjqxxxx is correct; there is a proof in Honsberger's Mathematical Gems III, which is short enough to reproduce here. In fact, it suffices to verify the following eight identities:

$F_{4k} - 1 = F_{2k+1} L_{2k-1}$ $F_{4k+1} - 1 = F_{2k} L_{2k+1}$ $F_{4k+2} - 1 = F_{2k} L_{2k+2}$ $F_{4k+3} - 1 = F_{2k+2} L_{2k+1}$ $F_{4k} + 1 = F_{2k-1} L_{2k+1}$ $F_{4k+1} + 1 = F_{2k+1} L_{2k}$ $F_{4k+2} + 1 = F_{2k+2} L_{2k}$ $F_{4k+3} + 1 = F_{2k+1} L_{2k+2}$

where $L_k$ are the Lucas numbers. These identities all follow straightforwardly from Binet's formula, although I imagine there are also combinatorial proofs.


I suspect at least one of these is an open problem, if not both. Let me record for now the following observation: modular arithmetic is not enough.

Proposition: For any finite set $p_1, ... p_n$ of primes, there exists a Fibonacci number $F_k$ such that $\prod p_i | F_k$.

Proof. Since $F_n | F_{mn}$ for all $m, n \ge 1$ it suffices to show this for a single prime. But the Fibonacci sequence is clearly periodic $\bmod p$ for any $p$ (since the Fibonacci recursion is reversible), and $F_0 = 0 \equiv 0 \bmod p$. (The computation of the exact period $\bmod p$ is a nice exercise.)

So both $F_n + 1$ and $F_n - 1$ can avoid any finite set of primes.

  • 1
    I find an identity in a paper just now. $F_n^2-F_{n-1}F_{n+1}=(-1)^{n-1}$ http://www.fq.math.ca/Scanned/8-1/daykin-a.pdf2011-01-10
11

Wikipedia cites the following source for the assertion that no sufficiently large Fibonacci number is one greater or one less than a prime:

Ross Honsberger, Mathematical Gems III (AMS Dolciani Mathematical Expositions No. 9), 1985, ISBN 0-88385-318-3, p. 133.

Not sure if that reference has a proof.

  • 0
    It does! I'm surprised. I'll add it to my answer and make it CW.2011-01-09