Question

The Fibonacci sequence is defined by $F_1 = F_2 = 1$ and $F_{n + 2} = F_{n + 1} + F_n$. Find the remainder when $F_{1999}$ is divided by 5.

Answer 1

The remainder is 1

Explanation:

Given the Fibonacci sequence

F_1 = F_2 = 1, and

F_(n + 2) = F_(n + 1) + F_n

We want to find the remainder when F_(1999) is divided by 5.

Let us write the first 20 numbers of the sequence in (mod 5). They are

F_1 = 1,

F_2 = 1,

F_3 = 2,

F_4 = 3,

F_5 = 5 = 0 (mod 5),

F_6 = 3,

F_7 = 3,

F_8 = 1

F_(9) = 4

F_(10) = 0

F_(11) = 4

F_(12) = 4

F_(13) = 3

F_(14) = 2

F_(15) = 0

F_(16) = 2

F_(17) = 2

F_(18) = 4

F_(19) = 1

F_(20) = 0

We have: 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0

Now, 1999 = 19(mod 20)

The 19th number in the sequence is 1.

So, the remainder is 1.