Consider the ordered pairs (f

_{n},f

_{n+1}) modulo

**N**, where

**N**is the natural number under consideration. There can only be a finite number of unique such pairs—certainly no more than

**N**

^{2}of them. Hence they must cycle at some point. If we set f

_{0}=0 and f

_{1}=1, that says there must eventually be some M>0 such that f

_{M}=0 (mod

**N**) and f

_{M+1}=1 (mod

**N**); this condition is sufficient but not necessary for

**N**| f

_{M}to be true. Why must we eventually have this condition? Because given f

_{n}and f

_{n+1}, we can calculate f

_{n-1}-- that is, the process can be run backward and cannot branch. The CACM answer said that the process can run backward ("Yeah, so what?" I thought) but because I'm slow, it didn't occur to me that since it can run backward, and produce a single result, we could not have the case where f

_{0}=0,f

_{1}=1 and then at some later point have f

_{X},f

_{X+1}(both nonzero), and at some even later point come back to f

_{X},f

_{X+1}and cycle that way without ever hitting (0,1) again.

Right. Next question: Given a number N, how far must you go to find a Fibonacci
number that's a multiple of N? I didn't answer that one; instead I took a very short
whack at calculating n>0 such that f_{n}≡0 (mod **N**)
and f_{n+1}≡1 (mod **N**). Of course a computer program
was involved (I think this is what happens to lazy math majors; they become
programmers). I wrote the following code before I understood the part about
"process can run backward", so...

def doit(the_base): apair = 0, 1 b2i = dict() for iter in range(99999): # arbitrary if not SILENT: print apair, if apair in b2i: if SILENT: return iter, b2i[apair] print '\nDone at %d: %s seen at %d' % ( iter, `apair`, b2i[apair]) break b2i[apair] = iter apair = (apair[1], (apair[0] + apair[1]) % the_base) else: print "You can't get here --- at least I hope not; base =", the_base sys.exit(1)I ran this for several values of

`the_base`and found what look like some interesting patterns. Now let φ(

**N**) be the smallest n>0 such that f

_{n}≡0(mod

**N**), f

_{n+1}≡1(mod

**N**). It seems that if

**N**=p

_{1}p

_{2}, p

_{1}≠p

_{2}, then φ(

**N**)=

**LCM**(φ(p

_{1}),φ(p

_{2})): for example φ(2)=3, φ(3)=8, φ(6)=24. and φ(5)=20, φ(11)=10, φ(55)=20

What about powers of primes? It appears that φ(p^{n})=p^{n-1}φ(p) for n>1. Since φ(2)=3, this predicts φ(4)=6, φ(8)=12,
φ(16)=24, φ(32)=48, φ(64)=96. And so it is.

But there are some surprises. Often φ(N)>N; but φ(19)=18, φ(21)=16 (**LCM**(φ(3)φ(7))), and so on.

After writing the above, I searched on "factors of fibonacci numbers" (no quotes) which led me to http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html; this has a lot more interesting stuff about Fibonacci numbers.

## No comments:

Post a Comment