Fibonacci multiples, solution 1

In a previous post, I challenged you to prove

If m evenly divides n, then F_m evenly divides F_n,

where F_n denotes the nth Fibonacci number (F_0 = 0; F_1 = 1; F_{n+2} = F_{n+1} + F_n).

Here’s one fairly elementary proof (though it certainly has a few twists!). Pick some arbitrary m \geq 1 and consider listing not just the Fibonacci numbers themselves, but their remainders when divided by F_m. For example, let’s choose m = 4, so we want to list the remainders of the Fibonacci numbers when divided by F_4 = 3.

Here are the first 17 Fibonacci numbers:


And here are their remainders when divided by F_4 = 3, represented graphically (red = 1, orange = 2, blank gap = 0):

Remainders of the first 17 Fibonacci numbers mod 3

And indeed, as we would expect if the theorem is true, every fourth remainder is zero: F_{4k} is evenly divisible by F_4. But there seems to be a bit more than that going on—the pattern of remainders we got is definitely not random! Let’s try F_5 = 5. Here are the remainders when the first 21 Fibonacci numbers are divided by 5:

The first 21 Fibonacci numbers mod 5

Hmm. Every fifth remainder is zero, as we expected… but the other remainders don’t seem to follow a nice pattern this time.

…or do they? Actually, if you stare at it long enough you’ll probably find some patterns there! Not to mention that I haven’t really shown you enough of the sequence. Here are the remainders of the first 41 Fibonacci numbers when divided by 5:

First 41 Fibonacci numbers mod 5

Aha! So it does repeat after all. We just hadn’t looked far enough.

And just for fun, let’s include some Fibonacci numbers mod F_6 = 8. These repeat much more quickly than for F_5.

Fibonacci numbers mod 8

OK, now that we’ve tried some specific values of m, let’s think about this more generally. When listing the remainders of the Fibonacci numbers divided by F_m, the initial part of the list will look like

F_0, F_1, F_2, \dots, F_{m-1}, 0

because all the Fibonacci numbers before F_m are of course less than F_m, so when we divide them by F_m they are simply their own remainder. Next, of course, F_m leaves a remainder of zero when divided by itself. Then what?

Well, F_{m+1} = F_m + F_{m-1} by definition, so its remainder mod F_m is F_{m-1}. OK, so far we have

F_0, F_1, F_2, \dots, F_{m-1}, 0, F_{m-1}

In fact, the rule for finding the next remainder in the sequence will be the same as the rule defining the Fibonacci numbers, except that we do everything mod F_m. So the next element in the sequence is 0 + F_{m-1} = F_{m-1} again:

F_0, F_1, F_2, \dots, F_{m-1}, 0, F_{m-1}, F_{m-1}

…and now, it seems, we are stuck! What do we get when we add F_{m-1} + F_{m-1}? Who knows?

Here is where I will do something sneaky. I am going to replace the second copy of F_{m-1} by -F_{m-2}, like this:

F_0, F_1, F_2, \dots, F_{m-1}, 0, F_{m-1}, -F_{m-2}

Huh!? What does that even mean? Surely we can never actually get a negative number as a remainder when dividing by F_m. Well, that’s true, but from now on, instead of strictly writing the remainder when F_k is divided by F_m, I’ll just write something which is equivalent to F_k modulo F_m. This is all that really matters, since I just want to see which positions are equivalent to zero modulo F_m.

So, the claim is that F_{m-1} \equiv -F_{m-2} \pmod{F_m}. Why is that? Well, F_{m-1} + F_{m - 2} = F_m \equiv 0 \pmod{F_m}, and then we can just subtract F_{m-2} from both sides.

Then what? F_{m-1} - F_{m-2} = F_{m-3}; then -F_{m-2} + F_{m-3} = -(F_{m-2} - F_{m-3}) = -F_{m-4}, and so on: we get the Fibonacci numbers in reverse, with alternating signs!

F_0, F_1, F_2, \dots, F_{m-1}, 0, F_{m-1}, -F_{m-2}, F_{m-3}, -F_{m-4}, \dots

For example, here are the first few Fibonacci numbers mod 8 again, but according to the above pattern, with negative numbers indicated by downwards pointing bars (and the original bars shown mostly transparent, for comparison):

See how the colors of the bars repeat now, but running forwards then backwards?

If m is even, then F_1 will be positive (as you can see in the example above); that is, we get

F_0, F_1, F_2, \dots, F_{m-1}, 0, F_{m-1}, -F_{m-2}, \dots, -F_2, F_1, 0, \dots

After this point we get F_1 + 0 = F_1, 0 + F_1 = F_2, and so on, and the whole pattern repeats again, as we’ve seen.

What if m is odd? Then F_1 will be negative, so we have to go through one more cycle with everything negated:

F_0, \dots, F_{m-1}, 0, F_{m-1}, -F_{m-2}, \dots, -F_1, 0, -F_1, -F_2, \dots, -F_{m-1}, 0, -F_{m-1}, F_{m-2}, \dots, F_1, 0

This explains why we had to look at a longer portion of the remainders mod 5 before they repeated. Here’s mod 5 again, with negatives shown graphically:

The colors of the bars still repeat: forwards, then backwards but alternating up and down, then forwards but all upside down, then backwards and alternating (but the other way). But at the end we’re back to F_1, so the whole thing will repeat again.

In any case, whether m is odd or even, these patterns of remainders will keep repeating forever, with a 0 always occurring every m positions—that is, at F_m, F_{2m}, F_{3m}, \dots, so F_{km} will always be divisible by F_m!

There are other ways to prove this as well; perhaps I’ll explain some of them in a future post. It turns out that the converse is also true: if F_m evenly divides F_n, then m must evenly divide n. I don’t know a proof off the top of my head, but maybe you can find one?

This entry was posted in fibonacci, modular arithmetic, number theory, pattern, pictures, proof, sequences and tagged , , , . Bookmark the permalink.

5 Responses to Fibonacci multiples, solution 1

  1. Zachary Abel says:

    Great explanation! I especially like the diagrams illustrating sign changes.

    I think your proof here also shows the converse: If k does not divide m, then the remainder of F_k modulo F_m is one of F_1,\ldots,F_{m-1} (possibly negated) and is therefore nonzero.

    • Brent says:

      Oh, hey, what do you know! I proved something without realizing it. What should we call this proof technique? “Proof by golly”?

  2. Pingback: Weekly Picks « — the Blog

  3. Pingback: Fibonacci numbers in Art « Wed-Gie

  4. Pingback: Fibonnaci Frency « ElephantsWind

Comments are closed.