mersenneforum.org > Math Fibonacci and Lucas factors
 Register FAQ Search Today's Posts Mark Forums Read

 2009-02-15, 20:51 #1 Raman 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 nth Fibonacci Number is given by the following formula: $f_n = \frac {1}{ \sqrt 5} \left[ \left( \frac {1 + \sqrt 5}{2} \right) ^n - \left( \frac {1 - \sqrt 5}{2} \right) ^n \right]$ Or is there any formula to instantly calculate the nth Fibonacci Number without using any floating point arithmetic at all? (2) As for Cunningham numbers, we have $a^k-1|a^{nk}-1$ This can be easily proved by factoring as follows: $a^{nk}-1 = (a^k-1) \sum_{i=0}^{n-1} a^{ik}$ I noticed that the same property holds for the Fibonacci Numbers and the Lucas Numbers too. How to prove it up, right that way? $f_k|f_{nk}$ (3) For Mersenne Numbers, we have that Any factor of the Mersenne number $M_n = 2^n-1$ will always be of the form $2kn+1$ if n is prime. Also that for Fermat Numbers, Any factor of the Fermat Number $F_n = 2^{2^n}+1$ will always be of the form $k.2^{n+2}+1$ I have good proofs of these theorems for Mersenne and Fermat Numbers. Similarly, I noticed that for Fibonacci Numbers, any factor of the nth Fibonacci Number, fn will always be of the form $2kn \pm 1$ if n is prime. How to prove this fact? For the Lucas Numbers $L_n = f_{n-1} + f_{n+1}$ Is it so, only of the form $2kn+1$ 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 $f_{n - \left( \frac{n}{5} \right) } = 0\ (mod\ n)$ Last fiddled with by Raman on 2009-02-15 at 20:54
2009-02-15, 21:29   #2

"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts

Quote:
 Originally Posted by Raman (1) A proof that the nth Fibonacci Number is given by the following formula: $f_n = \frac {1}{ \sqrt 5} \left[ \left( \frac {1 + \sqrt 5}{2} \right) ^n - \left( \frac {1 - \sqrt 5}{2} \right) ^n \right]$ Or is there any formula to instantly calculate the nth Fibonacci Number without using any floating point arithmetic at all?
Well, if you simply carry $\sqrt 5$ in that form through the calculations, instead of substituting a floating-point approximation, you find that all the odd powers of $\sqrt 5$ cancel out and you're left with an integer.

Quote:
 (2) As for Cunningham numbers, we have $a^k-1|a^{nk}-1$ This can be easily proved by factoring as follows: $a^{nk}-1 = (a^k-1) \sum_{i=0}^{n-1} a^{ik}$ I noticed that the same property holds for the Fibonacci Numbers and the Lucas Numbers too. How to prove it up, right that way? $f_k|f_{nk}$
The Fibonacci formula above can be restated as
$f_n = a \left[ b^n - c^n \right]$
where a, b, and c are constants.

Substitute $nk$ for $n$.

Last fiddled with by cheesehead on 2009-02-15 at 21:31

2009-02-15, 21:53   #3
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts

Quote:
 Originally Posted by cheesehead Well, if you simply carry $\sqrt 5$ in that form through the calculations, instead of substituting a floating-point approximation, you find that all the odd powers of $\sqrt 5$ cancel out and you're left with an integer.
What I meant was that, a fast Fibonacci calculator, such as this
could calculate fn 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:
$f_n = \begin{cases} 1 & \mbox{if } n = 1 \\ 1 & \mbox{if } n = 2 \\ f_{n-1}+f_{n-2} & \mbox{if } n \ge 3. \\ \end{cases}$

Indeed, I would like to see so a proof for (3) & (4), of course.

Last fiddled with by Raman on 2009-02-15 at 22:00

 2009-02-15, 22:00 #4 CRGreathouse     Aug 2006 32·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 n-1, 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 2009-02-15 at 22:00
2009-02-15, 22:31   #5
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

4E916 Posts

Quote:
 Originally Posted by CRGreathouse The Lucas sequences, I believe, have recurrences that allow calculating element 2n from elements n and n+1 (or n and n-1, I can't remember). The Fibonacci numbers are just a special case. The fast calculations formulas are based on these relations.
I agree so.

$x^2 - Px + Q = 0$
$P = 1, Q = -1$

$f_n = \frac {\alpha ^n - \beta ^n }{\alpha - \beta }$
$L_n = {\alpha ^n + \beta ^n }$

$L_n = \frac{f_n}{\sqrt 5}$

$f_n = \begin{cases} 0 & \mbox{if } n = 0 \\ 1 & \mbox{if } n = 1 \\ Pf_{n-1}-Qf_{n-2} & \mbox{if } n \ge 2. \\ \end{cases}$

$L_n = \begin{cases} 2 & \mbox{if } n = 0 \\ 1 & \mbox{if } n = 1 \\ PL_{n-1}-QL_{n-2} & \mbox{if } n \ge 2. \\ \end{cases}$

$\begin{cases} f_{2n} = L_nf_n \\ L_{2n} = L_n^2 - 2Q^n \\ \end{cases}$

Hence, the proofs of (1), (3) & (4) are being pending so, thus.

Last fiddled with by Raman on 2009-02-15 at 22:32

2009-02-15, 23:29   #6

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

Quote:
 Originally Posted by Raman What I meant was that, a fast Fibonacci calculator, such as this could calculate fn 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.
I was joking, or presuming use of Maple, Mathematica or some other such software that could handle symbols.

2009-02-16, 07:19   #7
wpolly

Sep 2002
Vienna, Austria

21910 Posts

Quote:
 Originally Posted by Raman I agree so. $L_n = \begin{cases} 2 & \mbox{if } n = 0 \\ 1 & \mbox{if } n = 1 \\ PL_{n-1}-QL_{n-2} & \mbox{if } n \ge 2. \\ \end{cases}$
should be

$L_n = \begin{cases} 2 & \mbox{if } n = 0 \\ P & \mbox{if } n = 1 \\ PL_{n-1}-QL_{n-2} & \mbox{if } n \ge 2. \\ \end{cases}$

2009-02-17, 12:53   #8
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts

Quote:
 Originally Posted by wpolly should be $L_n = \begin{cases} 2 & \mbox{if } n = 0 \\ P & \mbox{if } n = 1 \\ PL_{n-1}-QL_{n-2} & \mbox{if } n \ge 2. \\ \end{cases}$
Of course. Indeed, so, to summarize up, only.
$f_n = \begin{cases} 0 & \mbox{if } n = 0 \\ 1 & \mbox{if } n = 1 \\ Pf_{n-1}-Qf_{n-2} & \mbox{if } n \ge 2. \\ \end{cases}$

$L_n = \begin{cases} 2 & \mbox{if } n = 0 \\ P & \mbox{if } n = 1 \\ PL_{n-1}-QL_{n-2} & \mbox{if } n \ge 2. \\ \end{cases}$

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.

$\begin{cases} f_{2n} = L_nf_n \\ L_{2n} = L_n^2-2Q^n \\ \end{cases}$

for even indices,
along with

$\begin{cases} f_{2n-1} = f_n^2-Qf_{n-1}^2 \\ L_{2n-1} = L_nL_{n-1}-PQ^{n-1} \\ \end{cases}$

for odd indices.

As it is up so for modular exponentiation:

$a^n = \begin{cases} a & \mbox{if } n = 1 \\ (a^{\frac{n}{2}})^2 & \mbox{if } n\ is\ even \\ a (a^{\frac{n-1}{2}})^2 & \mbox{if } n\ is\ odd \\ \end{cases}$

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)
$f_k=a[b^k-c^k]$
where
$a=\frac{1}{\sqrt 5}$
for Fibonacci Numbers, and
$a=1$
for Lucas Numbers.
$b=\frac{1+ \sqrt 5}{2}$
$c=\frac{1- \sqrt 5}{2}$

$f_{nk} = a[b^{nk}-c^{nk}] = a[b^k-c^k] \sum_{i=0}^{n-1} ^{n-1}C_i b^{ik} c^{(n-1-i)k} = f_k \sum_{i=0}^{n-1} ^{n-1}C_i b^{ik} c^{(n-1-i)k}$

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 2009-02-17 at 13:10 Reason: The use of tools for subscription purposes.

 2009-02-17, 18:14 #9 fivemack (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 freshly-baked proofs when you clap your hands. We're not.
2009-02-17, 20:35   #10
CRGreathouse

Aug 2006

32×5×7×19 Posts

Quote:
 Originally Posted by fivemack 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 freshly-baked proofs when you clap your hands.
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?

 2009-02-21, 22:25 #11 Raman 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 $f_p = -1\ (mod\ p)\ if\ \left( \frac{P^2-4Q}{p} \right) = -1$ $f_p = 1\ (mod\ p)\ if\ \left( \frac{P^2-4Q}{p} \right) = 1$ (2) $If\ f_p = -1\ (mod\ p)\ then\ f_{p+1} = 0\ (mod\ p)$ $If\ f_p = 1\ (mod\ p)\ then\ f_{p-1} = 0\ (mod\ p)$ 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 $f_p$ will always be of the form $2kp+1$ or $2kp-1$, if p is prime. I now realize that, In the Pollard's p-1 test Since $a^{p-1} = 1\ (mod\ p)$, so, we have that, $a^{k(p-1)} = 1\ (mod\ p)$ for any multiplier k. If $p-1|R$, then $a^R = 1\ (mod\ p)$ We should then compute $GCD(a^R-1,N)$ thus, to give away the factor p, where $R = \prod _{i=1} ^k q_i^{\beta _i}$ $q_i$ are the primes till the B-limit, and that $q_i^{\beta _i} \le B$ $q_i^{\beta _i+1} > B$ In the William's p+1 factoring algorithm, somewhat acts as a hybrid p+1 and p-1 test. Sometimes acts as p+1 algorithm when $\left( \frac{P^2-4Q}{p} \right) = -1$ Acts as p-1 algorithm if $\left( \frac{P^2-4Q}{p} \right) = 1$ If $\left( \frac{P^2-4Q}{p} \right) = -1$, then $f_{p+1} = 0\ (mod\ p)$ So that, $f_{k(p+1)} = 0\ (mod\ p)$ If $p+1|R$, then $f_R = 0\ (mod\ p)$ Compute $GCD(f_R,N)$ If $\left( \frac{P^2-4Q}{p} \right) = 1$, then $f_{p-1} = 0\ (mod\ p)$ Thus, $f_{k(p-1)} = 0\ (mod\ p)$ If $p-1|R$, then $f_R = 0\ (mod\ p)$ Compute $GCD(f_R,N)$ Last fiddled with by Raman on 2009-02-21 at 22:32

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov And now for something completely different 9 2017-06-28 16:56 sweety439 And now for something completely different 17 2017-06-13 03:49 jocelynl Math 2 2010-09-23 21:32 robert44444uk Math 3 2007-05-19 07:15 geoff Factoring 13 2005-12-23 01:59

All times are UTC. The time now is 01:05.

Sat May 8 01:05:30 UTC 2021 up 29 days, 19:46, 0 users, load averages: 1.31, 1.46, 1.49