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 (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² of them. Hence they must cycle at some point. If we set f₀=0 and f₁=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,f₁=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₁p₂, p₁≠p₂, then φ(N)=LCM(φ(p₁),φ(p₂)): for example φ(2)=3, φ(3)=8, φ(6)=24. and φ(5)=20, φ(11)=10, φ(55)=20

What about powers of primes? It appears that φ(pⁿ)=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.