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]) break b2i[apair] = iter apair = (apair, (apair + apair) % 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 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 http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html; this has a lot more interesting stuff about Fibonacci numbers.