121k views
4 votes
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.

User Gronostaj
by
7.8k points

1 Answer

4 votes

Answer:

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.

User Mathter
by
7.9k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.