mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-09-05, 16:03   #1
chris2be8
 
chris2be8's Avatar
 
Sep 2009

32·227 Posts
Default Factoring near Fibonacci numbers.

Hello,

Do Fibonacci numbers -1 have algebraic factors? I've noticed some PRPs in factordb like (10*I(5545)-1)/9 where N-1 has a lot of small factors which makes me think I would be able to prove it prime if I knew how to factor it.

There are several other PRPs where N-1 or N+1 simplify to Fibonacci(whatever) +or- a small integer. Are they likely to have algebraic factors?

Chris
chris2be8 is offline   Reply With Quote
Old 2019-09-05, 16:14   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
Hello,

Do Fibonacci numbers -1 have algebraic factors?
No.

Quote:

There are several other PRPs where N-1 or N+1 simplify to Fibonacci(whatever) +or- a small integer. Are they likely to have algebraic factors?

Chris
No.

What is the point of this, anyway? We already have enough factoring projects
underway. We don't need another one.
R.D. Silverman is offline   Reply With Quote
Old 2019-09-05, 16:25   #3
sweety439
 
Nov 2016

281910 Posts
Default

Fibonacci number (>8) -1 cannot be prime

Fibonacci number (>2) +1 cannot be prime

Conjecture: For every k>1, there are infinitely many k*F(n)-1 primes and infinitely many k*F(n)+1 primes
sweety439 is offline   Reply With Quote
Old 2019-09-05, 16:51   #4
chris2be8
 
chris2be8's Avatar
 
Sep 2009

32·227 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
What is the point of this, anyway? We already have enough factoring projects
underway. We don't need another one.
I'm looking for a quick way to prove PRPs prime by N-1 or N+1. So an easy way to split off smallish factors would be enough.

Chris
chris2be8 is offline   Reply With Quote
Old 2019-09-05, 17:41   #5
axn
 
axn's Avatar
 
Jun 2003

115528 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
Do Fibonacci numbers -1 have algebraic factors?
Sort of, yes. I don't know why, but fibonacci(n)-1 is divisible by certain smaller fibonacci numbers. Perhaps the same reason cyclotomic polynomials-1 have factors.

I've gone ahead and added those for your number -- now it is provable.
axn is offline   Reply With Quote
Old 2019-09-05, 17:46   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

22×367 Posts
Default

I've worked out, (it was new for me), there is a factorization:
Code:
fibonacci(2*n+1)+(-1)^n=fibonacci(n+1)*(fibonacci(n+1)+fibonacci(n-1))
R. Gerbicz is offline   Reply With Quote
Old 2019-09-05, 18:15   #7
axn
 
axn's Avatar
 
Jun 2003

2·5·7·71 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
I've worked out, (it was new for me), there is a factorization:
Code:
fibonacci(2*n+1)+(-1)^n=fibonacci(n+1)*(fibonacci(n+1)+fibonacci(n-1))
I can see that fibonacci(2*n+1) - 2 has some interesting factors as well. Explanation?

BTW, since (fibonacci(n+1)+fibonacci(n-1)) = lucas(n), it got me to https://en.wikipedia.org/wiki/Lucas_...onacci_numbers which gives
F(n+k) + (-1)^k F(n-k) = L(k)F(n).
I bet that can explain these.
axn is offline   Reply With Quote
Old 2019-09-06, 03:38   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

29×157 Posts
Default

Quote:
Originally Posted by axn View Post
I can see that fibonacci(2*n+1) - 2 has some interesting factors as well. Explanation?

BTW, since (fibonacci(n+1)+fibonacci(n-1)) = lucas(n), it got me to https://en.wikipedia.org/wiki/Lucas_...onacci_numbers which gives
F(n+k) + (-1)^k F(n-k) = L(k)F(n).
I bet that can explain these.
Yes, that's on the right track.

The factorizations are related to the trigonometric identity

2*sin(A+B)-2*sin(A-B) = (2*sin(A))(2*cos(B))

and similar identities involving sums and differences of sines or of cosines.

Algebraically, "Fibonacci numbers act like sines, Lucas numbers act like cosines." Note that the difference in arguments on the right side is the second argument on the left side.

But there's a twist. The quadratic x^2 - x - 1 has constant term -1, not 1, so the two roots are negative-reciprocal, not reciprocal.

As a result, the form of the factorization "wig-wags," or alternates. I will illustrate with F2n+1 - 2, where, note that 2 = F3, and in each identity the indexes of the factors differ by 3.

F5 - F3 = 3 = L1F4

F7 - F3 = 11 = L5F2

F9 - F3 = 32 = L3F6

F11 - F3 = 87 = L7F4

[etc]

Also,

F5 + F3 = 7 = L4F1

F7 + F3 = 15 = L2F5

F9 + F3 = 36 = L6F3

F11 + F3 = 91 = L4F7

[etc]

There are similar identities involving Fm+2k + or - Fm, and slightly more complicated identities involving Lucas numbers.
Dr Sardonicus is offline   Reply With Quote
Old 2019-09-06, 15:45   #9
chris2be8
 
chris2be8's Avatar
 
Sep 2009

7FB16 Posts
Default

Thanks for that. Now I've got a suitable toolkit to deal with any similar PRPs that turn up.

Chris
chris2be8 is offline   Reply With Quote
Old 2019-09-07, 13:05   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

29×157 Posts
Default

The factorizations for sums and differences of Lucas numbers whose indexes differ by an even number are actually not that difficult to characterize. They may be described as follows (F indicates Fibonacci numbers, L indicates Lucas numbers):

Lm+2k - Lm = 5FkFk+m if k is even, and LkLk+m if k is odd

Lm+2k + Lm = 5FkFk+m if k is odd, and LkLk+m if k is even
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Another computationally useless sum for Fibonacci numbers Dr Sardonicus Puzzles 1 2018-07-21 03:19
Fibonacci numbers Citrix Math 27 2006-11-20 17:18
Another puzzle about Fibonacci numbers c00ler Puzzles 27 2006-04-17 20:27
Factoring Fibonacci/Lucas numbers geoff Factoring 13 2005-12-23 01:59
Fibonacci Numbers Vijay Programming 26 2005-04-15 19:11

All times are UTC. The time now is 00:25.

Wed May 19 00:25:38 UTC 2021 up 40 days, 19:06, 0 users, load averages: 2.00, 2.16, 1.97

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.