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?

  • 7
    $\begingroup$ Please improve the question's readability. Perhaps add the title into the body as well. $\endgroup$ – Asaf Karagila Jan 9 '11 at 10:23
  • $\begingroup$ This question is relevant to my interests $\endgroup$ – Listing Jan 9 '11 at 12:04
  • 2
    $\begingroup$ "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? $\endgroup$ – Qiaochu Yuan Jan 9 '11 at 13:53
  • $\begingroup$ @Qiaochu: Mathematica uses exact integers to do all this. $\endgroup$ – Mariano Suárez-Álvarez Jan 9 '11 at 14:35
  • $\begingroup$ @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. $\endgroup$ – Qiaochu Yuan Jan 9 '11 at 14:53

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.

  • $\begingroup$ Your proposition is lacking a product symbol (at least in my browser) $\endgroup$ – TonyK Jan 9 '11 at 14:12
  • $\begingroup$ @TonyK: there's an implied quantifier on i. But I guess I might as well be more precise. $\endgroup$ – Qiaochu Yuan Jan 9 '11 at 14:15
  • $\begingroup$ Implied quantifier? Fellow thinks he's Einstein. Anyway, +1 for listening :-) $\endgroup$ – TonyK Jan 9 '11 at 14:51
  • 1
    $\begingroup$ I find an identity in a paper just now. $F_n^2-F_{n-1}F_{n+1}=(-1)^{n-1}$ fq.math.ca/Scanned/8-1/daykin-a.pdf $\endgroup$ – a boy Jan 10 '11 at 3:25

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.

  • $\begingroup$ It does! I'm surprised. I'll add it to my answer and make it CW. $\endgroup$ – Qiaochu Yuan Jan 9 '11 at 17:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.