mersenneforum.org Factoring near Fibonacci numbers.
 Register FAQ Search Today's Posts Mark Forums Read

 2019-09-05, 16:03 #1 chris2be8     Sep 2009 32·227 Posts 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
2019-09-05, 16:14   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by chris2be8 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.

 2019-09-05, 16:25 #3 sweety439   Nov 2016 281910 Posts 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
2019-09-05, 16:51   #4
chris2be8

Sep 2009

32·227 Posts

Quote:
 Originally Posted by R.D. Silverman 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

2019-09-05, 17:41   #5
axn

Jun 2003

115528 Posts

Quote:
 Originally Posted by chris2be8 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.

 2019-09-05, 17:46 #6 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 22×367 Posts 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))
2019-09-05, 18:15   #7
axn

Jun 2003

2·5·7·71 Posts

Quote:
 Originally Posted by R. Gerbicz 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.

2019-09-06, 03:38   #8
Dr Sardonicus

Feb 2017
Nowhere

29×157 Posts

Quote:
 Originally Posted by axn 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.

 2019-09-06, 15:45 #9 chris2be8     Sep 2009 7FB16 Posts Thanks for that. Now I've got a suitable toolkit to deal with any similar PRPs that turn up. Chris
 2019-09-07, 13:05 #10 Dr Sardonicus     Feb 2017 Nowhere 29×157 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Dr Sardonicus Puzzles 1 2018-07-21 03:19 Citrix Math 27 2006-11-20 17:18 c00ler Puzzles 27 2006-04-17 20:27 geoff Factoring 13 2005-12-23 01:59 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