mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-02-15, 20:51   #1
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default 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
Raman is offline   Reply With Quote
Old 2009-02-15, 21:29   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts
Default

Quote:
Originally Posted by Raman View Post
(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
cheesehead is offline   Reply With Quote
Old 2009-02-15, 21:53   #3
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

Quote:
Originally Posted by cheesehead View Post
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
Raman is offline   Reply With Quote
Old 2009-02-15, 22:00   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default

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
CRGreathouse is offline   Reply With Quote
Old 2009-02-15, 22:31   #5
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

4E916 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
Raman is offline   Reply With Quote
Old 2009-02-15, 23:29   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by Raman View Post
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.
cheesehead is offline   Reply With Quote
Old 2009-02-16, 07:19   #7
wpolly
 
wpolly's Avatar
 
Sep 2002
Vienna, Austria

21910 Posts
Default

Quote:
Originally Posted by Raman View Post
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}
wpolly is offline   Reply With Quote
Old 2009-02-17, 12:53   #8
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

Quote:
Originally Posted by wpolly View Post
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.
Raman is offline   Reply With Quote
Old 2009-02-17, 18:14   #9
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13×491 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2009-02-17, 20:35   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by fivemack View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2009-02-21, 22:25   #11
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

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
Raman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucas and Fibonacci primes Batalov And now for something completely different 9 2017-06-28 16:56
Primes in n-fibonacci sequence and n-step fibonacci sequence sweety439 And now for something completely different 17 2017-06-13 03:49
factors of lucas sequences jocelynl Math 2 2010-09-23 21:32
Fibonacci modulo Fibonacci robert44444uk Math 3 2007-05-19 07:15
Factoring Fibonacci/Lucas numbers 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.