FIBONACCI NUMBERS IN MODULO N

NOTICING A CYCLE

• First we look at the last digit of each number in the Fibonacci numbers (Modulo 10) :

n a(n)

0 0

1 1

2 1

3 2

4 3

5 5

6 8

7 3

8 1

9 4

10 5

n a(n)

11 9

12 4

13 3

14 7

15 0

16 7

17 7

18 4

19 1

20 5

21 6

n a(n)

49 9

50 5

51 4

52 9

53 3

54 2

55 5

56 7

57 2

58 9

59 1

n a(n)

60 0

61 1

62 1

63 2

64 3

65 5

66 8

67 3

68 1

69 4

70 5

PISANO PERIOD • Fibonacci numbers:

• F(n)= F(n-1) + F(n-2)

• with seed values F(0)=0, F(1)=1

• Fibonacci numbers modulo n will always give a repeating sequence

• The period of this sequence is called a Pisano Period

• The nth Pisano period = π(n)

• Fibonacci numbers modulo 2:

• π(n) = 3

• Cycle = 011

• Sequence = 011011011011011011011011011…

• Fibonacci numbers modulo 3:

• π(n) = 8

• Cycle = 01120221

• Sequence =011202210112022101120221…

PROOF

• Let k and n be non-negative numbers, and let r = k mod n

• What is the range of r? R = { 0, 1, 2, … n-1} , |R| = n

• Each Fibonacci number is the sum of a pair numbers ( F(n-1), F(n-2) )

• In modulo n, each Fibonacci number is the sum of a pair of numbers ( F(n-1) mod n, F(n-2) mod n )

• Is the number of pairs finite? How many possible pairs are there?

• If a + b = c and a and b each have a finite range it follows that c will also have a finite range

• Therefore Fibonacci numbers in modulo n will eventually be the sum of a pair of numbers that have already been seen earlier in the series, this will conclude the cycle and the sequence will repeat from that point on

main (){ int n, m, temp, f0= 0, f1= 1; for (int k = 0; k < 10; k++); { cout << "Enter how many terms of the series to display:" << endl; cin >> n; cout << "Enter a value for m for the series F mod m:" << endl; cin >> m; cout << "The series F mod " << m << " is : " << endl; for ( int i =0; i < n; i++) { if (i <= 1) temp = i; else {

// f0 = f0 % m; // f1 = f1 % m; temp = f0 + f1; temp = temp % m; f0=f1; f1=temp; } cout << i << " " << temp << endl; } }return 0;}