Discussion Forum

Fibonacci Remainders - DMS Discussion

 
 
Picture of ZIML Admin
Fibonacci Remainders - DMS Discussion
by ZIML Admin - Wednesday, December 6, 2017, 12:12 PM
 

From the week of November 27 to December 1 we chose Monday's problem (that you can find here):

The Fibonacci sequence is defined by $F_1=F_2=1$, and $F_{n+2} = F_{n+1} + F_{n}$, that is, the first two terms are both $1$, and each subsequent term is the sum of the previous two terms. Find the reminder when $F_{2017}$ is divided by $7$.

55% of the students who tried the problem got it right on their first attempt.

The problem wants us to look at the $2017^{th}$ term of the Fibonacci sequence and find its remainder when we divide it by $7$.

One way to approach the problem could be find this number and proceed to divide it, however, this would take quite a long time and it is quite easy to make mistakes along the way. Definitely not the most efficient way to approach this problem. For the curious students, the $2017^{th}$ Fibonacci number has $422$ digits and is equal to $$\begin{array}{l} 15086391789600768130615036458536459937373801376224164974692009 \\ 22390276025246298126991260130021195541439868244005183272438348 \\ 72651121573283855615370408097976849656070442430462484685278878 \\ 14440899790425840452480830862551189745331010401938308776834838 \\ 41064322606527865298429664119611826719932524789088056935252825 \\ 16921275651815380115149089537108530787711541335005559273369791 \\ 42870501314336853488832335125625555755502836236097.\end{array}$$ I can't even count that far!

As we only want to look at the remainders, we can instead just work with the remainders of the numbers in the Fibonacci sequence and look for a pattern. Remember, the remainder of a sum of numbers is the same as the sum of their remainders. As we've discussed before in another post, when solving Number Theory problems that have to do with remainders, it is usually helpful to just look at the remainders.

So, instead of working with the Fibonacci sequence, we look at the sequence of remainders: $$\begin{array}{ccccccccc} F_1 = 1 & F_2 = 1 & F_3 = 1 + 1 = 2 & F_4 = 1 + 2 = 3 & F_5 = 2 + 3 = 5 & F_6 = 3 + 5 = 8 & F_7 = 5 + 8 = 13 & F_8 = 8 + 13 = 21 & F_9 = 13 + 21 = 34 & \dots \\ F_1 = 1 & F_2 = 1 & F_3 = 1 + 1 = 2 & F_4 = 1 + 2 = 3 & F_5 = 2 + 3 = 5 & F_6 = 3 + 5 = 1 & F_7 = 5 + 1 = 6 & F_8 = 1 + 6 = 0 & F_9 = 6 + 0 = 6 & \dots \end{array}$$

Can you see a pattern? Share your thoughts and questions below!