Inspired by Numberphile

Number Theory Level 2

Joe lost a bet to Bob. He had to pay a huge amount of candy! Here's how he went about it:

On the first day of school, Joe gave 1 piece of candy to Bob. On the second day, Joe gave 1 piece of candy to Bob. On the third day, Joe gave 2 pieces of candy to Bob. On the fourth day, Joe gave 3 pieces of candy to Bob. On the fifth day, Joe gave 5 pieces of candy to Bob.

In general, on the $nth$ day he gave $F_n$ pieces of candy, where $F_n$ is the $nth$ Fibonacci number. Joe pays like this until the 180th day of school.

In total he payed $x$ pieces of candy to Bob. Find $x$ $(mod 3)$

2 0 1

1 solution

Deb Sen
Apr 23, 2015

Take the first few Fibonacci numbers.

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987...

Now take the following mod 3

1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0

We see it repeats - (1,1,2,0,2,2,1,0)(1,1,2,0,2,2,1,0)- In cycles of 8.

Since Joe does this process till the 180th day: in every cycle of eight he pays 9 (mod 3) pieces of candy. 180/8= 22 R 4.

Because mods are distributive over addition, in the 22 cycles of 9 pieces of candy he pays, that is 0 (mod 3) because 9=0(mod 3) and that is the sum of the pieces of candy's he pays in every cycle of 8.

In the four remaining he pays from the first four in the cycle- 1+1+2=4

4=1(mod 3) And we're done.

Note: I have no idea why this recursion occurs. Could someone explain that?

Numberphile!!!

Colin Carmody - 6 years, 1 month ago

More generally, the Fibonacci sequence modulo any number m will repeat. It's called a Pisano period -- i.e. the smallest value r such F r is congruent 0 modulo m and F {r+1} is congruent to 1 modulo m where F n is the (n+1)-st Fibonacci number. NOTE: I am assuming the first Fibonacci number is F 0 = 0. In the 1700s Lagrange was one of the first to observe that the Fibonacci sequence modulo m is periodic. WHY? The sequence modulo m is completely determined by an pair of adjacent terms in the sequence, and there are only finitely many pairs of integers from the least residue class (i.e., possible remainders upon division by m) 0, 1, 2, . . . , m-1. In fact, exactly m^2 possible ordered pairs exist. Thus the sequence modulo m must eventually repeat some pair of adjacent numbers and hence is periodic.

In your example, there are only 9 pairs 0,0 0,1 0,2 1,0 1,1 1,2 2,0 2,1 2,2 Note 0,0 will never be a pair because then that would mean at some point, adjacent Fibonacci numbers are both divisible by 3 and hence all further sequence terms are ALL divisible by 3 which is nonsense. So there is only so long a sequence that can be written with 0's, 1, and 2's without eventually repeating a pair of adjacent numbers. In your case you observed that that the pair 1, 1.

Hey, this is my first day on this site by the way. I love Numberphile and the end of a video led me here! :) -aBa

aBa Math - 2 years, 12 months ago

I learned something new!

Theodore Warren (Student) - 2 years, 3 months ago

Inspired by Numberphile

1 solution

0 pending reports