mersenneforum.org > Math Fibonacci modulo Fibonacci
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-05-17, 13:31 #1 robert44444uk     Jun 2003 Suva, Fiji 23×3×5×17 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.
2007-05-17, 14:00   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts

Quote:
 Originally Posted by robert44444uk Anyway, I would proposed based on extremely limited observations that such integers exist and further, there are infinite integers that are never mod values.
There is no such thing as an "infinite" integer. Perhaps you mean "infinitely
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.

2007-05-17, 15:14   #3
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

2×7×461 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.

 2007-05-19, 07:15 #4 robert44444uk     Jun 2003 Suva, Fiji 37708 Posts Brilliant, than you Bob and Fivemack.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 17 2017-06-13 03:49 efeuvete Math 7 2013-05-26 11:24 MattcAnderson Math 7 2013-01-14 23:29 Citrix Math 27 2006-11-20 17:18 TTn Math 2 2002-10-25 21:47

All times are UTC. The time now is 23:15.

Tue Jan 31 23:15:07 UTC 2023 up 166 days, 20:43, 0 users, load averages: 1.43, 1.30, 1.17

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔