mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-10-09, 06:52   #1
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2·17 Posts
Default Factors of Fibonacci numbers

Greetings.
The factors of Fibonacci numbers:
For prime p:
F(p)=\prod_{i=1}^{m} (k_{i}\cdot p\pm 1)
For an any n
n=p_{1}^{t1}\cdot p_{2}^{t2}\cdot...\cdot p_{k}^{tk}

F(n)=\prod_{i=1}^{m} (k_{i}\cdot p_{1}\pm 1)\cdot (l_{i}\cdot p_{2}\pm 1)\cdot ...\cdot(z_{i}\cdot p_{k}\pm 1)

Example p=103
F(103)=1500520536206896083277=519121*5644193*512119709
(519121-1)/103=5040
(5644193+1)/103=54798
(512119709-1)/103=4972036

P.S.
Of course,m and coefficients k both are function of p or n)
RMLabrador is offline   Reply With Quote
Old 2020-10-10, 08:31   #2
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2·17 Posts
Default

Interesting. It is not so hard to write some simple code, like this (Pari GP)

forprime(n=11,900,x=Mod(factorint(fibonacci(n)),n);print(n,lift(x)))

and see, that posted above is true for all prime, at least for those, that in the scope of your patience))

Taking into account the level of your obsession with factorization 2 ^ n + 1 or so, my next post will be about it)))
RMLabrador is offline   Reply With Quote
Old 2020-10-11, 00:27   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

43·97 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
Greetings.
The factors of Fibonacci numbers:
For prime p:
F(p)=\prod_{i=1}^{m} (k_{i}\cdot p\pm 1)
For an any n
n=p_{1}^{t1}\cdot p_{2}^{t2}\cdot...\cdot p_{k}^{tk}
I note that F5 = 5 does not conform to your prescription.

The following is well known. It is an exercise for beginners in the subject of Fibonacci and Lucas numbers.

Let p be a prime number.

1) If (5/p) = +1 [p == 1 or 4 (mod 5)], then p divides Fp-1. Corollary: If (5/p) = +1, and p divides Fq with q prime, then q divides p-1, i.e. p == 1 (mod q).

2) If (5/p) = -1 [p == 2 or 3 (mod 5)], then p divides Fp+1. Corollary: If (5/p) = -1, and p divides Fq with q prime, then q divides p + 1, i.e. p == -1 (mod q).
Dr Sardonicus is offline   Reply With Quote
Old 2020-10-11, 16:30   #4
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

428 Posts
Default

i guess, "well known" is not true))
here, no mention about
http://www.maths.surrey.ac.uk/hosted....html#section2

and i can find 10+ links like this, and 0 link with similar formulae, like mine.
I just state the global form of factors of Fibonacci numbers, and not properties of F(n) itself.
Besides, 2,3,5 and 7 in my opinion are not prime.
They uber prime, they posses the rule of 1 and themselves division, and the broke the many other, i.e. 2 is even, 3 and 5 and 7 are too monadic) remember 6k+/-1? 6=2*3 and 6=5+1 and 6=7-1.
Forget this for a while.
RMLabrador is offline   Reply With Quote
Old 2020-10-11, 16:58   #5
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2·17 Posts
Default

Just run this in some other than Pari/GP system
x = 251;
c = Fibonacci[x];
(*Solve[(((a*x+c-1)/((a*x-1)*x))^(-1))-(1/b)==0&&(x*a-1)*(b*x-1)
==c,{a,b},Integers]*)
Solve[((a + b)^2 + 4*a*b*(c - 1) - z^2 == 0) && (x*a - 1)*(b*x - 1) -
c == 0 && b > a && a > 0 && z > 0, {a, b, z}, Integers]

Last fiddled with by RMLabrador on 2020-10-11 at 17:03 Reason: clear mind
RMLabrador is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring near Fibonacci numbers. chris2be8 Factoring 9 2019-09-07 13:05
Fibonacci and Lucas factors Raman Math 40 2010-07-19 03:30
Fibonacci numbers Citrix Math 27 2006-11-20 17:18
Another puzzle about Fibonacci numbers c00ler Puzzles 27 2006-04-17 20:27
Fibonacci Numbers Vijay Programming 26 2005-04-15 19:11

All times are UTC. The time now is 08:46.

Thu Jan 21 08:46:52 UTC 2021 up 49 days, 4:58, 0 users, load averages: 3.78, 3.57, 3.10

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.