20090215, 20:51  #1 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3·419 Posts 
Fibonacci and Lucas factors
I just came across an excellent relationship between the
properties of factors of Mersenne and Fibonacci Numbers. It will quite be obvious for already experienced people, but it is the first time, that I am coming across this fact. Can someone please point out to me, the proofs of the following theorems: (1) A proof that the n^{th} Fibonacci Number is given by the following formula: Or is there any formula to instantly calculate the n^{th} Fibonacci Number without using any floating point arithmetic at all? (2) As for Cunningham numbers, we have This can be easily proved by factoring as follows: I noticed that the same property holds for the Fibonacci Numbers and the Lucas Numbers too. How to prove it up, right that way? (3) For Mersenne Numbers, we have that Any factor of the Mersenne number will always be of the form if n is prime. Also that for Fermat Numbers, Any factor of the Fermat Number will always be of the form I have good proofs of these theorems for Mersenne and Fermat Numbers. Similarly, I noticed that for Fibonacci Numbers, any factor of the n^{th} Fibonacci Number, f_{n} will always be of the form if n is prime. How to prove this fact? For the Lucas Numbers Is it so, only of the form if n is prime? (4) Finally, thus I will need so for a proof of the most important theorem, that is the Fibonacci pseudoprime test, that is: If n is prime, then Last fiddled with by Raman on 20090215 at 20:54 
20090215, 21:29  #2  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1111000001100_{2} Posts 
Quote:
Quote:
where a, b, and c are constants. Substitute for . Last fiddled with by cheesehead on 20090215 at 21:31 

20090215, 21:53  #3  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts 
Quote:
could calculate f_{n} instantly, for the values of n, as high as 20000000. I asked what arithmetic (without floating point) was responsible for calculating that value without examining all the previous Fibonacci numbers. You haven't given me the proof for the Fibonacci number formula from the following recurrence relation, at all, at once: Indeed, I would like to see so a proof for (3) & (4), of course. Last fiddled with by Raman on 20090215 at 22:00 

20090215, 22:00  #4 
Aug 2006
3^{2}·5·7·19 Posts 
The Lucas sequences, I believe, have recurrences that allow calculating element 2n from elements n and n+1 (or n and n1, I can't remember). The Fibonacci numbers are just a special case.
The fast calculations formulas are based on these relations. Last fiddled with by CRGreathouse on 20090215 at 22:00 
20090215, 22:31  #5  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
4E9_{16} Posts 
Quote:
Hence, the proofs of (1), (3) & (4) are being pending so, thus. Last fiddled with by Raman on 20090215 at 22:32 

20090215, 23:29  #6  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:


20090216, 07:19  #7 
Sep 2002
Vienna, Austria
219_{10} Posts 

20090217, 12:53  #8 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts 
Of course. Indeed, so, to summarize up, only.
And then finally, these two are the formula that helps so to accelerate the calculations of the Fibonacci and Lucas Numbers, by without using any floating point arithmetic tools at all, thus. for even indices, along with for odd indices. As it is up so for modular exponentiation: Ok, that (1) can be proved so by Mathematical Induction, though I prefer to see a proof for it, by using derivation. If in case, you don't know how that form will be, how will you derive it so, starting up right from the scratch, thus? I accept up so the proof for (2) where for Fibonacci Numbers, and for Lucas Numbers. What about for the other 2 cases, of them? Why is nobody responding up so to (3) & (4) as yet, at all, after this case? Thus, are people still ignoring towards me up so? Of course, right that way, thus. Last fiddled with by Raman on 20090217 at 13:10 Reason: The use of tools for subscription purposes. 
20090217, 18:14  #9 
(loop (#_fork))
Feb 2006
Cambridge, England
13×491 Posts 
I'm not responding to you because of your tone of voice; you are sounding as if the people on this forum are your servants, ready to bring you freshlybaked proofs when you clap your hands.
We're not. 
20090217, 20:35  #10 
Aug 2006
3^{2}×5×7×19 Posts 
Maybe we're going about this wrong. Perhaps we should be giving suggestions about how to find a mathematician willing to consult on the problem?

20090221, 22:25  #11 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3·419 Posts 
I am not ordering you to give me the proofs. Just give me hints simply on how to go ahead with the problem. These proofs cannot be found out anywhere in the web. I have to proceed on with my college project work.
After thorough analysis of the p+1 Factoring algorithm, I need the following proofs: It will also be useful for Lucas Lehmer Test and Lucas Lehmer Riesel too. (1) If p is prime, then prove that (2) These two are the main results. But, well and good if it can also be proved that: (3) Any factor of the Lucas Sequence Number will always be of the form or , if p is prime. I now realize that, In the Pollard's p1 test Since , so, we have that, for any multiplier k. If , then We should then compute thus, to give away the factor p, where are the primes till the Blimit, and that In the William's p+1 factoring algorithm, somewhat acts as a hybrid p+1 and p1 test. Sometimes acts as p+1 algorithm when Acts as p1 algorithm if If , then So that, If , then Compute If , then Thus, If , then Compute Last fiddled with by Raman on 20090221 at 22:32 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Lucas and Fibonacci primes  Batalov  And now for something completely different  9  20170628 16:56 
Primes in nfibonacci sequence and nstep fibonacci sequence  sweety439  And now for something completely different  17  20170613 03:49 
factors of lucas sequences  jocelynl  Math  2  20100923 21:32 
Fibonacci modulo Fibonacci  robert44444uk  Math  3  20070519 07:15 
Factoring Fibonacci/Lucas numbers  geoff  Factoring  13  20051223 01:59 