Fibonacci Sequence

Sequence defined by

and initial condition
It has a formula

Tiling a One-Dimensional Rectangle
Fibonacci Matrix

Theorem

Given prime :

Proof

It turns out that is the number of ways of tilling a cycle
Now let act on the set of tilings of cycle by rotation.
As , every tiling has an orbit of size except the tiling with only tiles.
But then the number of tilings up to permutation is:

Thus has to divide

Theorem (Wall, 1960)

If is prime and ,
then and
and has period

Proof

Using Quadratic Reciprocity
exists
if and only if

if and only if

Now use

and apply Fermat’s Little Theorem to find

The previous theorem implies so .
Also so the period is .