Finally catching up on stuff from a week ago, when David Wilson said:

For which m for do the Fibs have every residue mod m?

As David Terr implicitly pointed out, if we miss a residue mod m, we do for all multiples of m as well -- so it's reasonable to ask about the prime moduli first. It's easy to check that you hit all moduli for 2,3,5,7. I just wrote the two-minute c program which tells me those are the only primes under 250,000 for which it works. I was surprised -- but perhaps only half as surprised as you, since I followed up Mike Stay's reference to Marc Renault's master's thesis, and thence to D. D. Wall's "Fibonacci Series Modulo $m$", in the Monthly (67 #6, Jun-Jul 1960, pp 525-532; on Jstor, if you have institutional access). He proves: (1) If p is +-1 mod 10, then the period of the Fib's mod p divides p-1 (2) If p is +-3 mod 10, then the period of the Fib's mod p divides 2p+2 Incidentally, the separation into these two cases is because of the sqrt(5) in the golden ratio, which either does (case 1) or doesn't (case 2) exist in the integers mod p -- that's another math-fun discussion I was just catching up on :-). Anyway, since there are p residues mod p, this immediately tells us that primes ending in 1 or 9 can't possibly have all the moduli. (That's why I was only half as surprised.) If it really is true that 2/3/5/7 are the only primes that have all the moduli, we're playing a game of four-dimensional chomp, and there is a finite set of "minimal" (with respect to the divisor ordering) numers which fail, and all others succeed. We know easily that 8 and 49 fail, limiting our growth in that direction. Again from Mike Stay's reference, we know that all powers of 5 succeed. I just checked up to 3^14 and 15^7 and those both succeed. Oh, and 18, 21 and 28 are in the minimal fail set -- probably that all has to do with non-relatively-prime periods, but I haven't had the time to think about that. Go ahead, someone, prove it fails for all primes over one digit, and succeeds for 15^n for all n... --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.