## 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 $n$th 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: $0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987$

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

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:

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:

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$.

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? 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: Fibonacci numbers in Art « Wed-Gie

3. Pingback: Fibonnaci Frency « ElephantsWind