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?

  • 5
    Please improve the question's readability. Perhaps add the title into the body as well.2011-01-09
  • 0
    This question is relevant to my interests2011-01-09
  • 2
    "Always" is not the same as "holds true in the first 10,000 cases" in mathematics. Also, are you sure you enabled arbitrary precision arithmetic to do this computation?2011-01-09
  • 0
    @Qiaochu: Mathematica uses exact integers to do all this.2011-01-09
  • 0
    @Mariano: I wasn't sure what language this was, and when I tried to duplicate the results in Matlab I ran into the precision problem, so I thought it was worth mentioning.2011-01-09
  • 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

17

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.

  • 0
    Your proposition is lacking a product symbol (at least in my browser)2011-01-09
  • 0
    @TonyK: there's an implied quantifier on i. But I guess I might as well be more precise.2011-01-09
  • 0
    Implied quantifier? Fellow thinks he's Einstein. Anyway, +1 for listening :-)2011-01-09
  • 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