I have stumbled upon a weird connection between the fibonacci sequence and prime numbers which I'd like to share with you for critique. It may well have been discovered before or be a simple extension to already known theories but I'd thought I'd throw it out here and see if anyone can help me understand why this is.
let f(n) be the fibonacci sequence, where f(1) = 1, f(2) =1 and f(n) =f(n-1) + f(n-2)
let p be any prime number
then there exists f(x) such that x <= p+1 and p divides f(x).
In other words, for any prime number p, p will divide into an element in the fib sequence of length p+1.
Are there any number theorists out there who can help me understand why this is ?
some (numerical) examples..
take p = 11, the sequence is ( 1,1,2,3,5,8,13,21,34,55,89,144 ). 11 divides 55.
take p = 113, 113 divides 4181, 39088169, 365435296162,
3416454622906707, 31940434634990099905, 298611126818977066918552 (in the fib seq).
take p = 1019, 1019 divides
25114976279235567401141687729968217201284416410339 36987096543961011972029158855122390289687985563592 24697935541899985687078834370062374556001083802897 84045499406705400799446671092387273627245867460595 373893159959 (in the fib seq).
Now I originally thought that as I was choosing x numbers and that all I needed was for f(x) | p = 0, then this could happen out of chance,
but the limit of the probability of this happening by chance 1-e^-1 ( approx 63%), so I've searched (numerically) for a counter example... I can't find one yet.
If p is not prime, then the above does not hold true (although it does for some values). I haven't gone into too much research as to the properties of p (if not prime) cause it to be true.