# Is every $N$th Fibonacci number where $N$ is divisible by $5$ itself divisible by $5$

There seems to be a pattern of sorts in the Fibonacci sequence:

The $$5$$th, $$10$$th, $$15$$th & $$20$$th values are:

$$5, 55, 610, 6765$$

Does this pattern continue ad infinitum? I've tried a few more using Binet's Formula and it seems to hold. So:

Is every $$N$$th Fibonacci number where $$N$$ is divisible by $$5$$ itself divisible by $$5$$?

Bonus Q: Are there any other patterns?

• crypto.ku.edu.tr/5th-Fibonacci and for another pattern, see: math.stackexchange.com/questions/2462222/… Jan 29, 2018 at 9:41
• If you want to investigate yourself, there is a relationship between Fibonacci and Lucan numbers which would enable you to prove that $F_n|F_{kn}$ for all positive integers $n$ and $k$. Always more satisfying to do yourself and you have Binet and the equivalent expression for Lucas nos not too difficult to find a useful expression for $F_{n+m}$ (induction is also a route) Jan 29, 2018 at 9:42
• Fibonacci numbers is an example of a strong divisibility sequence. It satisfies for all positive integers $m, n$. $\gcd(a_m,a_n) = a_{\gcd(m,n)}$. As a corollary, $a_m | a_{km}$ for any positive integers $k,m$ . Since $F_5 = 5$, you have $5 = F_5 | F_{5k}$ for every $k$. Jan 29, 2018 at 9:46
• Actually $$\nu_5(F_k) = \nu_5(k).$$ Jan 29, 2018 at 12:55
• I discussed some relationships between Fibonacci numbers and primes here Jan 29, 2018 at 15:28

The answer is YES.

Use induction for $n=1, 2, ...$

$F_{5\cdot1}=5$ holds so we have a basis for induction.

Suppose $F_{5k}=5t$ for some $t\in\mathbb{N}$. Then consider $n=k+1$:

\begin{align}F_{5k+5}&=F_{5k+3}+F_{5k+4}\\&=2F_{5k+3}+F_{5k+2}\\&=2(F_{5k+2}+F_{5k+1})+F_{5k+1}+F_{5k}\\&=3F_{5k+1}+2F_{5k+1}+F_{5k}+2F_{5k}\\&=5F_{5k+1}+3(5t)\\&=5(F_{5k+1}+3t)\end{align} This is clearly divisible by $5$ so $5\mid F_{5n}$ for $n\in\mathbb{N}$.

Let us make a table of the Fibonacci sequence modulo $5$. If we can find two occurrences of the same two terms modulo $5$ with all the $F_{5k}$ (between those two occurence) being $0$ modulo $5$, we can prove this statement.

$$\begin{array}{c|c|c|} \text{F_1 to F_5} & \text{1} & \text{1} & \text{2} & \text{3} & \text{0} \\ \text{F_6 to F_{10}} & \text{3} & \text{3} & \text{1} & \text{4} & \text{0} \\ \text{F_{11} to F_{15}} & \text{4} & \text{4} & \text{3} & \text{2} & \text{0} \\ \text{F_{16} to F_{20}} & \text{2} & \text{2} & \text{4} & \text{1} & \text{0} \\ \text{F_{21} to F_{25}} & \text{1} & \text{1} & \text{2} & \text{3} & \text{0} \\ \end{array}$$

Since $F_1$ and $F_2$ are the same as $F_{21}$ and $F_{22}$, and $F_5$, $F_{10}$, $F_{15}$ and $F_{20}$ are all $0$, then this cycle repeats indefinitely, and hence $F_{5k} \equiv 0 \pmod 5$.

• This is useful. I'd only run the modulo up to F20 so I missed the emerging pattern. Jan 29, 2018 at 13:16
• @RobbieDee Yeah, the problem is that 20 is the period, so you need 25 to verify it ;-)
– yo'
Jan 29, 2018 at 16:35
• @RobbieDee Thanks for the upvotes! I'm surprised no one used this method, but it doesn't take too long until you see a pattern (because $5$ is a small number). Jan 29, 2018 at 22:53

If $F_n$ is divisible by $5$, then so is $F_{n+5}$ because $$F_{n+5} = 8 F_n + 5 F_{n-1}$$ The result follows by induction. The base of the induction is $F_5=5$, which is divisible by $5$. (You can also use $F_0=0$.)

• – lhf
Jan 29, 2018 at 13:13

Yes, if $5$ divides $n$ then $5$ divides $F_n$. Actually also the other way round is true, so $5$ divides $n$ if and only if $5$ divides $F_n$.

More generally, the following congruence holds $$F_n\equiv n3^{n-1}\pmod{5}.$$ This congruence implies our claim and more than that. For example, it follows that the Fibonacci sequence modulo $5$ is periodic with period length $5\cdot 4=20$ where $5$ is the period of $n$ and $4$ the period of $3^{n-1}$ (recall that by Fermat's little theorem $3^{k(5-1)}\equiv 1 \pmod{5}$). The list of values $F_n\pmod{5}$ is $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n \pmod{20}& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 &9\\ F_n\pmod{5} &\mathbf{0}& 1& 1& 2& 3& \mathbf{0}& 3& 3& 1& 4\\ \hline n \pmod{20}&10& 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18&19\\ F_n\pmod{5} &\mathbf{0}& 4& 4& 3& 2& \mathbf{0}& 2& 2& 4& 1 \\\hline \end{array}$$

Proof of the above congruence $F_n\equiv n3^{n-1}\pmod{5}$. By the Binet's formula and the binomial theorem we have that \begin{align}F_n&=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)\\ &=\frac{1}{2^{n}\sqrt{5}}\sum_{k=0}^{n}\binom{n}{k}\left((\sqrt{5})^k-(-\sqrt{5})^k\right)\\ &=\frac{1}{2^{n}\sqrt{5}}\sum_{j=0}^{\lfloor (n-1)/2\rfloor}\binom{n}{2j+1}\left((\sqrt{5})^{2j+1}-(-\sqrt{5})^{2j+1}\right)\\ &=\frac{1}{2^{n}\sqrt{5}}\sum_{j=0}^{\lfloor (n-1)/2\rfloor}\binom{n}{2j+1}(2\sqrt{5}\cdot 5^j)\\ &=\frac{1}{2^{n-1}}\sum_{j=0}^{\lfloor (n-1)/2\rfloor}\binom{n}{2j+1}5^j \equiv 3^{n-1}\sum_{j=0}^{0}\binom{n}{2j+1}5^j\equiv n3^{n-1}\pmod{5}. \end{align}

We know that the fifth Fibonacci number is $5$. Then, we let this be $x$th number. The next number is defined by the $(x+x-1)$th number. The next will be $(2x-1+x)$th. Then the next is $(3x-1+2x-1)$th. The next is $(8x-3)$. The next is $(13x-5)$. This means that the $(5k+5)$th term can be expressed as $13\times 5k$th term $-5$. This is evidently a multiple of 5, since the first term with $5k=5$, $5$, is a multiple of $5$.

The fibonacci series follows the same rule as $$\frac{a^n-b^n}{a-b}$$ as applied to integers. Here, $$a=\frac 12\sqrt{-1}; \ b=\frac 12\sqrt{-5}$$. They are in essence, repunits, or numbers written entirely in '1's. So 111 will divide 6 and 9 1's but not 7 or 10.

If some number $$x$$ divides some $$F_y$$, then it divides every $$F_{yz}$$. As with ordinary numbers, it suffices to deal with prime and prime powers, the composite numbers being a weak multiplication (eg LCM for product), so 10 divides $$F_{15n}$$ for all n, and no other.