# Fibonacci sequence divisible by 7? [closed]

Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$.

I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.

Look at the sequence $F_n$ reduced mod $7$:

1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0, 1,1,2.. and it repeats forever


Since the only places where it is 0 are $n=8,16$ this proves that $7|F_n \iff 8|n$.

General theory of recurrence relations.

Definition A $k$th order recurrence relation on some set $X$ is a function $a : \mathbb N \rightarrow X$ with $k$ initial values i.e. $a(1),\cdots,a(k)$ defined and for all $i > k$, $a(i+k+1) = f(a(i),a(i+1),\cdots,a(i+k))$. Note that a $k$th order recurrence is also a $k+1$th order recurrence.

Notation We generally write the elements of a $k$th order recurrence relation as $(a_n)$.

Definition Recurrence relation homomorphisms, let $(a_n)$ be a $k$th order recurrence relation on the set $X$ defined by the map $f : X^k \rightarrow X$ (as well as some initial values). A map $\varphi : X -> Y$ is called a recurrence relation homomorphism on $a$ when there exists $f' : Y^k \rightarrow Y$ satisfying the commutative diagram $\varphi \circ f = f' \circ \varphi$.

Theorem Recurrence relation homomorphisms produce recurrence relations. Suppose we are given a recurrence relation homomorphism in the notation above. The claim is that $b_n = \varphi(a_n)$ is also a $k$th order recurrence relation.

Proof Clearly $k$ initial values are given, further for $i > k$ we have $b_{i+k+1} = \varphi(f(a_{i},a_{i+1},\cdots,a_{i+k})) = f'(\varphi(a_{i}),\varphi(a_{i+1}),\cdots,\varphi(a_{i+k}))) = f'(b_{i},b_{i+1},\cdots,b_{i+k}).$

Example The "reduction mod m" map $\varphi : \mathbb Z \rightarrow \mathbb Z/m\mathbb Z$ as described here is a recurrence homomorphism on any recurrence defined by a polynomial. To see this note that homomorphisms on rings (such as $\varphi$) can be lifted to homomorphisms on polynomial rings over the respective rings. That induces the map from $f$ to $f'$.

Example Call the Fibonacci sequence $(F_n)$ reduced mod 7: $(S_n)$, this is a recurrence by the general example above. Note that $F_n \equiv S_n \pmod 7$.

Theorem Initial segments may be discarded. Suppose $a_n$ is a recurrence relation of order $k$, then $b_n = a_{n+h}$ for any constant $h$ is also a recurrence relation of order $k$.

Proof Initial values are computed easily, if $f$ is the function defining elements of $a$ then $f$ also defines elements of $b$, to see this note that for $i > k$ we have $b_i = a_{i+h} = f(a_{i+h},a_{i+1+h},\cdots,a_{i+k+h}) = f(b_{i},b_{i+1},\cdots,b_{i+k})$.

Theorem Periodicity. Suppose the recurrence relation $b_n$ is defined as $a_{n+h}$ (both being $k$th order), if they share the first $k$ initial values then they are equal everywhere.

Proof Induction on $n$ in the stronger proposition that for all $i \le n$, $a_i = b_i$.

• base case (n = k): This is the hypothesis of the theorem.

• recursive step ($n \implies n+1$): Since for every $i \le n$, $a_i = b_i$ we have $a_{n+1} = f(a_{n-k},a_{n-k+1},\cdots,a_{n}) = f(b_{n-k},b_{n-k+1},\cdots,b_{n}) = b_{n+1}$ (since they are both defined by $f$).

Example Define $S'_n = S_{n+16}$ they share the first two initial values therefore they are equal everywhere.

Example Define $S_n^r = S_{n+16\cdot r}$ by induction these are all equal: The base case $r=0$ is trivial and the recursive step $r \implies r+1$ comes form an adaptation of the previous example and transitivity.

Theorem $7|F_n \iff 8|n$.

Proof By the previous examples we have seen that $F_n \equiv F_{n+16\cdot r} \pmod 7$, furthermore a direct computation of the first 16 values of $S_n$ (at the top) shows that $F_n \equiv 0 \pmod 7 \iff n = 0+16 \cdot r,8+16\cdot r$ this is equivalent to $8|n$ and $x = 0 \pmod m$ is equivalent to $m|x$.

• It's the right observation but there's no proof here.
– lhf
Apr 24, 2011 at 1:47
• I'd be happier with an induction but I see now that you've listed the whole sequence mod 7 until a cycle appears, so it's ok.
– lhf
Apr 24, 2011 at 11:31
• @quanta: As it's written, I wouldn't call it a rigorous proof (in a homework assignment, I wouldn't give full points), but if I was talking to a college, I wouldn't want him to tell me more, so in this sense it's indeed complete. Apr 24, 2011 at 12:51
• @quanta: Because you didn't explicitly write why it repeats forever. I'm pretty sure you fully understand what you're writing in your answer, and I gave you +1 for it since it's the easiest (and hence best) answer here, but I can't look into your mind and see if you really understand everything: If you were a student of mine whom I don't know well, I'd subtract a point; if you were a studied mathematician, I'd expect exactly the answer you gave above and no more. Apr 24, 2011 at 13:02
• @quanta: Wow, I certainly didn't expect you to fill so many details. As for your last comment, I'm thinking both as a researcher and a scientist. As a researcher, I was perfectly happy with your original answer (so I upvoted it since I thought "ah, that makes is clear", not "this is a rigorous proof"), but I wanted to point out that someone who just starts learning these things really shouldn't think that this was a complete rigorous proof. The meaning of "complete rigorous" of course depends very much on your level of knowledge. Apr 24, 2011 at 18:25

A more pedestrian approach of induction, looking at the first 16 fibonacci numbers, the only 2 which are divisible by 7 are $f_8=21$ and $f_{16}=987$. Conjecture that $f_n$ is divisible by 7 if and only if $n$ is divisible by 8, as you mention in the comments. Using these observations as the base case, assume the result holds for all $f_j$ for $j\leq n$. Notice

$$f_{n+1}=21f_{n-6}+13f_{n-7}$$

which can be worked out by continually applying the recursive definition of the fibonacci sequence. This equation makes the induction follow pretty easily.

• Alternatelly one can use the $F$ matrix $(1 1 \\ 1 0)$ and check it's 8'th power. The first row gives your relation, anyhow the entire matrix is $(f_8 f_7 \\ f_7 f_6)$ which mod 7 is $(-1 0 \\ 0 1 )$. Apr 24, 2011 at 17:58
• @user9176 Note that your matrix is simply the matrix form of the shift map mentioned in my answer. Here linearity is in fact irrelevant. All that matters is that the shift map is invertible, so a permutation, so its orbits are cycles; e.g. see the nonlinear recursion in my answer. Apr 25, 2011 at 2:01

Hint  The shift map $$\rm\:n\to n+1\:$$ on pairs $$\rm\:(f_{n-1},\:f_n)\,\ \ (mod\ 7)\,$$ is an invertible map on a finite set, so is a permutation, so its orbits are cycles. Below is a further hint from one of my old sci.math posts. See this answer for much more.

A sequence f(n) satisfies the relation $$\rm\,f(n+2) = f(n+1)^2 - f(n),\,$$ with $$\rm \,f(1) = 39\,$$ and $$\rm \,f(2) = 45.\,$$ Prove that $$1986$$ divides infinitely many terms of the sequence.

Since the recursion determines unique values $$\rm\:f_{n+2},\:f_n\:$$ when run fore/backward, the shift map on the sequence induces a permutation $$\rm\:F\:$$ on integer pairs $$\rm mod\ 1986\!:\ \ F(f_n,f_{n+1})\ =\ (f_{n+1},f_{n+2})\ \quad i.e.\quad F(a,b)\: =\ (b,\,b^2-a)\ \$$ But $$\:0\:$$ occurs in the cycle containing $$(39,45)$$ since $$\rm\:F(39,45)\: =\: (45,0),\:$$ so $$\:0\:$$ occurs infinitely often in this finite cycle when $$\rm\:F\:$$ is iterated.

This replaces less formal arguments elsewhere on "repeated blocks" by rigorous arguments on standard structures (permutations and their cycle decomposition), thus clarifying the essence of the matter. One should strive to learn to recognize these abstractions in the wild, else one will be doomed to continually reinvent the wheel (here cycle).

• Wouldn't you also need to prove that $F^{\text{something}}(39,45) = (39,45)$? Apr 23, 2011 at 23:27
• @quanta Since $\rm\:F\:$ is permutation its orbits are cycles. That's the key point. In that sci.math thread other folks where proving this from scratch "reinventing the wheel (cycle)". Apr 23, 2011 at 23:39
• How is it seen that F is a permutation? Apr 23, 2011 at 23:48
• @quanta: Hint: it's an invertible map on a finite set - see the sentence that begins "Simpler". Apr 24, 2011 at 0:44

There is a cool thing with the Fibonacci and number 7, it transforms to a sequence of 16 number that repeat infinitely.

0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0

If you keep with the sequence you can see there is a 0 every 8th position so this let us with two slices of sequence.

s1 : 1,1,2,3,5,1,6 s2 : 6,6,5,4,2,6,1

So finobacci in module 7 will be like: 0s10s20s10s2........

If you take a consecutive s1 , s2 and add them number by number:

s1 : 1,1,2,3,5,1,6

s2 : 6,6,5,4,2,6,1 +

7,7,7,7,7,7,7


Which in module 7 is 0 so Fibonacci is transformed into a sequence of infinite 0.

So the process will be the following: 1. Module 7 to Fibonacci sequence.

0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0....

1. Group them by groups of 8 numbers.

2. If you take all groups of s1 and add them with their respective s2, consecutive. The result should be an infinite sequence of 0.

The Fibonacci sequence is a special case of the more general family of Lucas sequences. Hence, the theory pertaining to the Lucas and companion Lucas sequences necessarily applies to the Fibonacci sequence.

That being said, the first place that $$7$$ divides the $$F_{n}$$ sequence is when $$n = 8$$. Hence, the "rank of apparition'' of $$7$$ in the $$F_{n}$$ sequence is $$8$$. That is, $$\omega(7) = 8$$. Moreover, for Lucas sequences, and thus for the Fibonacci sequence, a prime $$p$$ divides the Fibonacci sequence at a term, $$F_{k}$$ if and only if $$k$$ is some multiple of $$\omega(p)$$; that is, $$p$$ divides every term and only those terms of the said sequence whose index $$k = m\omega(p),$$ for every positive integer $$m$$. Hence, the only terms of the Fibonacci sequence that contain $$7$$ as a factor are

$$F_{8}, F_{16}, F_{24}, \ldots.$$