Sunday, October 02, 2011

Does every natural number divide some Fibonacci number?

This puzzle came from a recent CACM. The answer, given in the subsequent issue, was "yes", but I had to think about the explanation before I got it. I'll leave a little whitespace here so you can avoid reading the explanation if you want to think about it some first.

Consider the ordered pairs (fn,fn+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 N2 of them. Hence they must cycle at some point. If we set f0=0 and f1=1, that says there must eventually be some M>0 such that fM=0 (mod N) and fM+1=1 (mod N); this condition is sufficient but not necessary for N | fM to be true. Why must we eventually have this condition? Because given fn and fn+1, we can calculate fn-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 f0=0,f1=1 and then at some later point have fX,fX+1 (both nonzero), and at some even later point come back to fX,fX+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 fn≡0 (mod N) and fn+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])
        b2i[apair] = iter
        apair = (apair[1], (apair[0] + apair[1]) % the_base)
        print "You can't get here --- at least I hope not; base =", the_base
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 fn≡0(mod N), fn+1≡1(mod N). It seems that if N=p1p2, p1≠p2, then φ(N)=LCM(φ(p1),φ(p2)): for example φ(2)=3, φ(3)=8, φ(6)=24. and φ(5)=20, φ(11)=10, φ(55)=20

What about powers of primes? It appears that φ(pn)=pn-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; this has a lot more interesting stuff about Fibonacci numbers.

No comments: