20070517, 13:31  #1 
Jun 2003
Oxford, UK
19×103 Posts 
Fibonacci modulo Fibonacci
Just playing around with Fibonaccis and I notice, at least for small Fibonaccis, that there are integers 6,9,14,15,16,17,19 which never appear as mod values for Fibonaccis mod (any Fibonacci).
For example: F(11)=89 is mod 1,2,4,1,11,5,21,34,0,89,89..... the first 13 Fibonacci numbers, 89 repeating thereafter. Looking at it the other way around, the first 44 Fibonaccis 1,1,2,3,5,8,13,21,34,55,89,144,233.... are 1,2,3,4,5,8,13,21,34,55,0,55,55,21,76,8,84,3,87,1,88,0,88,88,87,86,84,81,76,68,55,34,0,34,34,68,13,81,5,86,2,88,1,0 mod 89 and then the pattern repeats for the next 44 Fibonaccis. Interestingly, the series 6,9,14,15,16,17,19.. does not appear in OEIS and therefore it is unclear to me if this property has been investigated. Anyway, I would proposed based on extremely limited observations that such integers exist and further, there are infinite integers that are never mod values. Maybe some mathematically minded person can (i) point me to the name of this property, and its proof or disproof, or (ii) prove or disprove either of these propositions. 
20070517, 14:00  #2  
Nov 2003
2^{2}·5·373 Posts 
Quote:
many"??? The question you ask (rephrased) is whether the range of F_n mod F_m is Z. This is a somewhat interesting question. I will look into it if I can find the time. A secondary question would be to ask for the DENSITY (in Z) of the set F_n mod F_m if it is not all of Z. 

20070517, 15:14  #3  
(loop (#_fork))
Feb 2006
Cambridge, England
6441_{10} Posts 
Quote:
eg: mod F{14} we have 0 1 1 2 3 5 8 13 21 34 55 89 144 233 0 233 144 89 55 34 21 13 8 5 3 2 1 1 and then the sequence repeats mod F{11} we have 0 1 1 2 3 5 8 13 21 34 55 0 55 34 21 13 8 5 3 2 1 1 0 1 1 2 3 5 8 13 21 34 55 0 55 34 21 13 8 5 3 2 1 1 and then the sequence repeats So the sequence is a subset of 'what numbers are the difference of two Fibonacci numbers'; since the Fibonacci numbers grow exponentially, the density of their differences is 0. And you'll never find excitingly small differences because, if you want the difference of two Fibonacci numbers to be 76 then you know that the larger can be no more than the Fibonacci number three beyond 76 (ie 233) because F_n  F_{nm} is at least F_{n2}. And indeed 76 = 8913. 

20070519, 07:15  #4 
Jun 2003
Oxford, UK
19×103 Posts 
Brilliant, than you Bob and Fivemack.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primes in nfibonacci sequence and nstep fibonacci sequence  sweety439  And now for something completely different  17  20170613 03:49 
Odd Fibonacci pseudoprimes  efeuvete  Math  7  20130526 11:24 
Fibonacci Formula  MattcAnderson  Math  7  20130114 23:29 
Fibonacci numbers  Citrix  Math  27  20061120 17:18 
Fibonacci sums?  TTn  Math  2  20021025 21:47 