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 .