Will Nicholes

Fibonacci numbers and Pisano periods

The Fibonacci numbers (sequence A000045) form one of the most important and well-known sequences in mathematics.

The sequence is very easy to construct: start with 0 and 1 as the first two numbers in the sequence, and after that, every new term in the sequence is the sum of the previous two:

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

If we drop everything except the rightmost digit of each number in the sequence (A003893), we can see that those digits will eventually repeat:

0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7,
0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9,
0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3,
0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1,
0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7...

There are exactly 60 terms in this sequence before it begins repeating. This is known as its Pisano period. By considering only the rightmost digit, we are looking at the Fibonnaci numbers modulo 10.

There are different Pisano periods for different divisors. For example, here are the Fibonacci numbers, modulo 9 (A007887):

0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8,
0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1,
0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8...

In this case the numbers repeat after 24 terms, so for this sequence mod 9 the Pisano period is 24.

The Pisano periods for mod 1, 2, 3, etc. are 1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48... (sequence A001175.)

Let’s return to mod 10. There are 100 different pairs of decimal digits: i.e. 0,0; 0,1; 0,2... 9,8 and 9,9. But only 60 of these pairs appear in the mod 10 sequence (keeping in mind that each of the 60 terms can act as either the first or second digit in a pair.) Where are the other 40 pairs?

It turns out they appear in different, but related, sequences. Here are the Fibonacci-like sequences that appear mod 10:

The periods of these 6 sequences add up to 100: 1 + 60 + 20 + 3 + 12 + 4, which is what we’d expect for a mod 10 sequence.

Similarly, for mod 9 there are 81 possible pairs, of which only 24 appear in the main sequence, so the remaining 57 pairs must appear in different mod 9 sequences, as we’ll see below.

Table 1 below shows all of the Fibonacci-like sequences for mod 1 through mod 16.

Legend for Table 1

Table 1

The yellow-shaded cells indicate the start of a new modulus; the green-shaded cells indicate the row containing the fundamental Pisano period for that modulus (sequence A001175.)

See also sequence A161553, which lists the fundamental sequences for the green-shaded rows.

Below is a more compact version of the above table, showing the periods but not the sequences themselves.

Table 2