This exercise concerns the reduction of the Fibonacci sequence in various moduli

Question

This exercise concerns the reduction of the Fibonacci sequence in various moduli Suppose you know the value of the following Fibonacci numbers modulo 3: F_78 congruent 2 (mod 3) and F_79 congruent 1 (mod 3). Reduce F_80 (mod 3). Justify your answer. Find the first several numbers in the Fibonacci sequence, F_1, F_2, F_3, ellipsis, reduced modulo 3. Does the resulting sequence eventually become periodic? If so, continue writing terms until the sequence repeats. Find the first several numbers in the Fibonacci sequence reduced modulo 7. Does the resulting sequence eventually become periodic? If so, continue writing terms until the sequence repeats. Find the first several numbers in the Fibonacci sequence reduced modulo 6. Does the resulting sequence eventually become periodic? If so, continue writing terms until the sequence repeats Imagine writing the Fibonacci sequence modulo 12 out to the 150th term (but do not actually do so). Explain how you know that the sequence will start repeating before this term Let m isin N. Explain how you know that the Fibonacci sequence reduced modulo m is eventually periodic.

Explanation / Answer

We know;

a = x(mod p) and b = y(mod p);

we have (a+b) = (x+y)(mod p);

F78 = 2(mod 3)

F79 = 1(mod 3);

so F80 = F79+F78 = (2+1)(mod 3);

F80 = 3(mod 3) or 0(mod 3);

b) F1=1; F1=1(mod 3)

F2 = 1(mod 3)

F3 = F1+F2= 2(mod 3);

F4 = F3+F2=3(mod 3)= 0(mod 3);

F5 = F4+F3 = 2(mod 3);

F6 = F5+F4 = 2(mod 3);

F7 = F6+F5= 4(mod 3) = 1(mod 3);

F8 = 0(mod 3);

F9=1(mod 3);

F10 = 1(mod 3);

After 8th term pattern is repeating itself;

c)F1 = 1(mod 7);

F2=1(mod 7);

F3=2(mod 7);

F4 = 3(mod 7);

F5=5(mod 7);

F6=8(mod 7) = 1(mod 7);

F7 = 6(mod 7);

F8 = 7(mod 7) = 0(mod 7);

F9 = 6 (mod 7)

F10 = 6(mod 7);

F10 = 12(mod 7) = 5(mod 7);

F11=11(mod 7) = 4(mod 7);

F12=9(mod 7) = 2(mod 7);

F13=6(mod 7);

F14=1(mod 7);

F15 = 7(mod 7) = 0(mod 7);

F16 = 1(mod 7);

F17 = 1(mod 7);

Hence Repeatition started after F15;

d) after mod 6 also becomes periodic;

because

0   0
1   1
1   1
2   2
3   3
5   5
8   2
13   1
21   3
34   4
55   1
89   5
144   0
233   5
377   5
610   4
987   3
1597   1
2584   4
4181   5
6765   3
10946   2
17711   5
28657   1
46368   0
75025   1
121393   1

After F25 it started repeating itself;

e) As 12 = 2*6 it also started repeating after F25;

f) For modulo to be periodic it must reach to 0(mod m);

and eventually the number will become 0(mod m);

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.