Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

2 Answers 2

up vote 15 down vote accepted

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.

share|improve this answer
    
Your proposition is lacking a product symbol (at least in my browser) –  TonyK Jan 9 '11 at 14:12
    
@TonyK: there's an implied quantifier on i. But I guess I might as well be more precise. –  Qiaochu Yuan Jan 9 '11 at 14:15
    
Implied quantifier? Fellow thinks he's Einstein. Anyway, +1 for listening :-) –  TonyK Jan 9 '11 at 14:51
1  
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 –  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.

share|improve this answer
    
It does! I'm surprised. I'll add it to my answer and make it CW. –  Qiaochu Yuan Jan 9 '11 at 17:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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