# Proving that every integer has a Fibonacci number multiple

Show that for any positive integer, there exists a Fibonacci number N such that N is divisible by the integer.

I'm not really sure how to begin my approach to this problem, would really appreciate any help!

• Hint: Consider the sequence of FIbonacci numbers mod $n$. – MJD Nov 10 '15 at 22:10
• See the arguments given, eg, here: math.stackexchange.com/questions/744308/… – lulu Nov 10 '15 at 22:13

Modulo $n$ the Fibonacci sequence is periodic (because $F_k=F_{k-1}+F_{k-2}$ and there are only finitely many possibilities for what congruence classes $F_{k-1}$ and $F_{k-2}$ can belong to), and $F_0=0\equiv0$, which means there must be some later number $i$ for which $F_i\equiv 0$.

Edit: As the discussion in the comments have pointed out, the gaps in this "proof" are a bit too wide for comfort, here is a more thorough proof.

Lemma. For any natural number $n$ there are two distinct natural numbers $k\neq k'$ such that $F_k \equiv F_{k'}\pmod n$ and $F_{k-1} \equiv F_{k'-1}\pmod n$.

Proof: Make a list of all the possible pairs $(F_k, F_{k-1})$. This list is infinite, but reduced modulo $n$, there are only $n^2$ possible distinct pairs $(a, b)$. By the pidgeonhole principle, we must at some point get a pair $(F_k, F_{k-1})$ which represents the same pair as an earlier $(F_{k'}, F_{k'-1})$ when regarded modulo $n$ (we can even conclude immediately that $k, k' \leq n^2$, but that doesn't matter, really). This finishes the proof of the lemma.

Given a natural number $n$, and $k \neq k'$ as in the lemma, we see that $F_k\equiv F_{k'}$ and $F_{k-1}\equiv F_{k'-1}$ implies $F_{k-2} \equiv F_{k'-2}$ (all congruences are modulo $n$). This is because of the Fibonacci recurrence relation which states that $F_{j - 2} = F_j - F_{j+1}$ (after rearranging). If the right-hand side for index $k$ is congruent to the right-hand side with index $k'$, then the same must be true for the left-hand sides.

Therefore, if $k, k'$ are as in the lemma, then so are $k-1, k'-1$. This means that any time we have such a pair, we can subtract $1$ from each of them and get a new pair. This we can keep going until one of them reaches $0$, and the other one ends up being $|k-k'|$. That means that $0 = F_0 \equiv F_{|k-k'|}$, and since $k \neq k'$, we are finished.

• How do you prove it is periodic modulo $n$? – Gregory Grant Nov 10 '15 at 22:12
• That statement makes sense to me, but although I see how it is periodic I don't understand how to prove the periodicity of the sequence, could you please elaborate? – user282727 Nov 10 '15 at 22:13
• How do you prove that the periodic part contains residue $0$? The sequence $0,1,2,1,2,1,2 \dots$ is ultimately periodic modulo $3$ but doesn't contain infinitely many values $0$. So you need to show why $0$ recurs. – Mark Bennet Nov 10 '15 at 22:19
• @misaka For any two $n,n'$ such that $F_{n-1}\equiv F_{n'-1}$ and $F_{n-2}\equiv F_{n'-2}$ we will have $F_{n+m}\equiv F_{n'+m}$ for any $m$ (for instance by induction). That means that the sequence repeats with a period that divides $n-n'$. Also, such $n$ and $n'$ will always exist because there are only finitely many congruence classes. – Arthur Nov 10 '15 at 22:19
• @MarkBennet You can use the recurrence relation to define Fibonacci numbers for negative indices as well, and the proof in my previous comment will work regardless of the sign of $n,n'$ and $m$. Therefore it must be periodic already at index $0$. – Arthur Nov 10 '15 at 22:22