Thread: Fibonacci modulo Fibonacci View Single Post
2007-05-17, 15:14   #3
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

193616 Posts

Quote:
 Originally Posted by robert44444uk 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).
Well, the Fibonacci numbers have very small period modulo the Fibonacci numbers; F(2n), F(3n), F(4n) are divisible by F(n), F(4n+1) is always 1 mod F(n) so the period is at most 4n, and if n is even then F(2n+1)=1 mod F(n) so the period is 2n.

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_{n-m} is at least F_{n-2}. And indeed 76 = 89-13.