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

I solved it and wrote up my solution.

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

We start with the following useful lemma.

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$