Source

I got this problem from Rustan Leino, who got it from Carroll Morgan.

I solved it and wrote up my solution.

Problem

Prove that for any positive $K$, every $K$th number in the Fibonacci sequence is a multiple of the $K$th number in the Fibonacci sequence. More formally, for any natural number $n$, let $F(n)$ denote Fibonacci number $n.$ That is, $F(0) = 0,$ $F(1) = 1,$ and $F(n+2) = F(n+1) + F(n).$ Prove that for any positive $K$ and natural $n$, $F(nK)$ is a multiple of $F(K).$

Solution
Reveal

We start with the following useful lemma.

**Lemma.** For any integers $i \geq 0,$ $j \geq 0,$ and $m > 0$ such
that $F(i) \equiv 0 \pmod m$, we have $F(i+j) \equiv F(j)F(i+1) \pmod m.$

*Proof.* We prove this by induction on $j.$ For the base cases, we
use $j=0$ and $j=1,$ each of which is obvious. For the inductive case, we
prove it's true for $j=J$ given that it's true for $j=J-1$ and $j=J-2.$ By
the definition of $F,$ we know $F(i+j) = F(i+j-1) + F(i+j-2).$ By the
inductive hypothesis, $F(i+j-1) \equiv F(j-1)F(i+1) \pmod m$ and $F(i+j-2)
\equiv F(j-2)F(i+1) \pmod m.$ So, their sum must satisfy $F(i+j) \equiv
F(j-1)F(i+1) + F(j-2)F(i+1) \pmod m.$ Now, $F(j) = F(j-1) + F(j-2),$ so we
see that $F(i+j) \equiv F(j)F(i+1) \pmod m,$ which is what we were trying
to prove. This concludes the induction. $\Box$

We now prove the statement that, for any integers $K > 0$ and $n \geq 0$, $F(nK) \equiv 0 \pmod{F(K)}.$ We prove this by induction on $n.$ The $n=0$ case is obvious, so we proceed to the inductive step where we prove it for $n=N$ given that it holds for $n=N-1.$ So, we know that $F((N-1)K) \equiv 0 \pmod{F(K)}$ and must prove that $F(NK) \equiv 0 \pmod{F(K)}.$ We apply the lemma using $i = (N-1)K,$ $j = K,$ and $m = F(K).$ So, we have $F((N-1)K + K) \equiv F(K)F((N-1)K+1) \pmod{F(K)}.$ The right side of this equivalence is a multiple of $F(K),$ so it must be congruent to $0$ modulo $F(K).$ Thus, $F((N-1)K + K) \equiv 0 \pmod{F(K)}.$ Since $(N-1)K + K = NK,$ we have proven the inductive case and completed the induction. Since the statement is equivalent to what we needed to prove, the proof is complete. $\Box$