Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How would you go about to prove that the final digits of the Fibonacci numbers recur after a cycle of 60?

References:

The sequence of final digits in Fibonacci numbers repeats in cycles of 60. The last two digits repeat in 300, the last three in 1500, the last four in , etc. The number of Fibonacci numbers between and is either 1 or 2 (Wells 1986, p. 65).

http://mathworld.wolfram.com/FibonacciNumber.html

share|improve this question
    
Why do you conjecture that? Do you have a reference that asserts the statement? –  Giovanni De Gaetano Feb 26 '12 at 9:52
    
I added some references. –  sic2 Feb 26 '12 at 9:57
    
Neat! Have a look at this link. –  Juan S Feb 26 '12 at 10:00

4 Answers 4

up vote 4 down vote accepted

Notice that:

$F_{n+15} = 7F_n$ mod $10$.

For all $n\geq 1$.

Also the order of $7$ mod $10$ is $4$ so the repetition in the digits of the Fibonacci numbers begins after place $15\times 4 = 60$.

share|improve this answer
    
I got that recursion by just writing out the first $16$ Fibonacci numbers mod $10$ and noticing that you get $1,1,...,7,7,...$, this dictates that that next $13$ numbers must be $7$ times their corresponding numbers (mod $10$) in the first lot of $15$ numbers. –  fretty Feb 26 '12 at 10:03
    
How do we know that F_n+15 = 7F_n mod 10 ? and How do you get that 7 mod 10 is 4 ? thanks. –  sic2 Feb 26 '12 at 10:07
    
Write out the first 16 Fibonacci numbers mod 10: 1,1,...,7,7,... Now by the recursion of the fibonacci numbers the fact that this "multiple-repeat" has happened now tells us that the next 13 numbers must be the same as the 3rd-15th Fibonacci numbers but multiplied by $7$ mod 10. So an actual repeat will happen as soon as we have multipled by enough $7$'s to get $1$ mod 10. This is the "order" of $7$ mod $10$. It is easy to work out here, $7^2 \equiv 4$ mod $10$ and $7^4 \equiv 1$ mod $10$ so the order is $4$. –  fretty Feb 26 '12 at 10:13
    
@sic2 He's not saying that $7\mod10$ is $4$, but rather that $7^4\equiv 1\mod 10$ and that this is not true for any smaller power of $7$, which is a consequence of Euler's theorem. –  Alex Becker Feb 26 '12 at 10:15
    
Also this method generalises to the Fibonacci numbers mod $n$. Find the first $1,1,...,a,a,...$ then work out the order of $a$ mod $n$ and you will have your first place where it recurs. –  fretty Feb 26 '12 at 10:29

Note that

$$ \begin{pmatrix} F_{n+1}\\ F_{n+2} \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix} $$

and

$$ \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{60} \equiv \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \mod 10. $$

One can verify that $60$ is the smallest power for which this holds, so it is the order of the matrix mod 10. In particular

$$ \begin{pmatrix} F_{n+60}\\ F_{n+61} \end{pmatrix} \equiv \begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix} \mod 10 $$

so the final digits repeat from that point onwards.

share|improve this answer
1  
The same matrix applies to the Lucas Numbers, however, $\text{ mod }10$, they have a period of $12$. The fact that $\begin{pmatrix} 0&1\\1&1\end{pmatrix}^{60}=\begin{pmatrix}1&0\\0&1\end{pmatrix}\text{ mod }10$, says that the period of a sequence satisfying $a_n=a_{n-1}+a_{n-2}$ divides $60$. –  robjohn Feb 26 '12 at 19:21

Since each term in the Fibonacci sequence is dependent on the previous two, each time a $0\pmod{m}$ appears in the sequence, what follows must be a multiple of the sequence starting at $F_0,F_1,\dots=0,1,\dots$ That is, a subsequence starting with $0,a,\dots$ is $a$ times the sequence starting with $0,1,\dots$

Consider the Fibonacci sequence $\text{mod }2$: $$ \color{red}{0,1,1,}\color{green}{0,1,1,\dots} $$ Thus, the Fibonacci sequence repeats $\text{mod }2$ with a period of $3$.

Consider the Fibonacci sequence $\text{mod }5$: $$ \color{red}{0,1,1,2,3,}\color{green}{0,3,3,\dots} $$ Thus, the Fibonacci sequence is multiplied by $3\pmod{5}$ each "period" of $5$. Since $3^4=1\pmod{5}$, the Fibonacci sequence repeats $\text{mod }5$ with a period of $20=4\cdot5$.

Thus, the Fibonacci sequence repeats $\text{mod }10$ with a period of $60=\operatorname{LCM}(3,20)$.

share|improve this answer

$F_{0}=F_1=F_{60}=F_{61}= 1 \mod10$

By inspection, these are the first two pairs of consecutive Fibonaccis for which this is true. Since the recurrence relation only takes into account the previous two terms and last digits only depend on previous last digits, this suffices to prove the claim.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.