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!
 A: 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.
