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?

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
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.