Every (Nonzero) Integer Divides Some Fibonacci Number

We denote the Fibonacci sequence as $(F_n)$ where $F_1=F_2=1$ and $F_{n+2}=F_{n+1}+F_n$ for $n\ge 1$. What we want to prove is that for any integer $m\ge 2$, there is some positive integer $k$ such that $m$ divides $F_k$.

It might be handy to rather start the sequence as $F_0=0$, $F_1=1$.

Our goal is to analyze the remainders of the terms $F_1,F_2,...$ when divided by $m$. It gives us a lot of insight to do this for a particular $m$, say $m=5$. Then the remainders of $F_0,F_1,F_2,...$ respectively are the following:

$$0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,\mid0,1,1,2,3,\dots$$

From this, we may conjecture that the sequence is periodic modulo $m$, which we will prove. (The length of this period is called the Pisano period, denoted by $\pi(m)$.)

The reasoning has two steps:

**1) We show that eventually, the sequence will be periodic. **Since every term of the Fibonacci sequence is determined by the previous two terms, it is enough to show that there is some pair of residues mod $m$ which appears twice as the residue of two consecutive terms in the sequence. (If the pairs $(F_i,F_{i+1})$ and $(F_{i+p},F_{i+p+1})$ have the same residue, then $F_{i+2}$ and $F_{i+p+2}$ etc. will also have the same residue.) This is easy using the box principle - as there are $m^2$ different possible pairs of modulo $m$ residues, if we look at the $m^2+1$ pairs

$$(F_0,F_1),(F_1,F_2),\dots,(F_{m^2},F_{m^2+1}),$$

there must be two which yield the same residue pair.

**2) We show that this periodicity goes backwards too. **Just note how the later terms of the Fibonacci sequence determine the previous terms as well, namely $F_n=F_{n+2}-F_{n+1}$. It follows that if $F_i,F_{i+1},...$ and $F_{i+p},F_{i+p+1},...$ have the same residues mod $m$, then so will $F_{i-1},...,F_0$ and $F_{i+p-1},...,F_p$.

This concludes the proof of periodicity. It follows that $m$ divides some Fibonacci number - $F_{\pi(m)}$ does the job. $\blacksquare$

The result that there is a Fibonacci number divisible by $m$ may be fundamental in the theory of Fibonacci numbers, but the proof itself is more important than the statement. This proof can be applied in the most unexpected circumstances, it is a powerful tool in proving that some term in a certain sequence reappears. To do so, we only require the ingredients for 1) and 2), namely that the sequence has finitely many possible terms, every term is determined by at most $C$ of the previous terms, and each term may be decoded from the terms after it.

Prove that there is a Fibonacci number with $2015$ zeros at its tail.

Prove that, there is a Fibonacci number which has $2015$ zeros in its tail.

Prove that for any integer $m\ge 2$ and for any integer $a$ relatively prime to $m$, there exists a positive integer exponent $k$ for which $m\mid a^k-1$.

Prove the estimate $\pi(m)\le m^2-1$.

Prove that there is a Fibonacci number whose base $10$ representation ends with $999999$.