Fibonacci Matrix

Let

Then

for the Fibonacci Sequence.

Theorem

If prime and then

Proof

Follows from Wall’s Theorem.

Theorem

If prime and then

So the period but .

Proof

Notice if and with

so if has period then has period dividing . Conversely if is invertible then the period of must divide that of . It is invertible so long as

which is impossible for . Then all starting points must have the same period. Let be minimal such that . Then

is a Group which acts on

by left multiplication sending

But as all elements of are invertible, no has any fixpoints except for the identity which has . All equivalence classes under multiplication by have size Therefore

so and thus We know that:

so

and we finally get thus: