Fibonacci
Repetition of pattern:
When each Fibonacci number is divided by 4, the Fibonacci remainders are:
1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, ...
The pattern 1, 1, 2, 3, 1, 0 repeats continuously.
Notation: When a Fibonacci number Fn is divided by k, then the remainder is denoted by Kn.
In general, we will show that there is a number m so that
Kim+j = Kj for all i ≥ 0 and j ≥ 0.
That is to say, when each Fibonacci number is divided by k, then the remainders are:
K1,K2,...,Km,K1,K2,...
The pattern K1,K2,...,Km
goes on forever.
Proof:
(K1,K2), (K2,K3), (K3,K4), ..., (Kk2+1,Kk2+2) is a sequence of k2+1 pairs of numbers.
The number of different pairs is at most k2,
for both coordinates can never be larger than k-1.
So, in this sequence of pairs of numbers there are duplicates. Say, (Kp,Kp+1) = (Kq,Kq+1).
Choose p and q as small as possible (p<q). Now we show that p=1.
Kp = Kq
and so Fp and Fq have the same remainder when divided by
k, and just as well Fp+1 and Fq+1.
But this includes that Fp-1 = Fp+1 - Fp and
Fq-1 = Fq+1 - Fq also have the same remainder
when divided by k and so Kp-1 = Kq-1 and
(Kp-1,Kp) = (Kq-1,Kq).
This is impossible, for p and q have the smallest possible values. Apparently (Kp-1,Kp)
is not an element of the sequence of pairs of numbers, and that is only possible when p = 1.
Therefore p = 1. Choose m = q-1.
We have proven: Km+1 = K1 and Km+2 = K2.
Now, you can easily proof by induction that Km+j = Kj for all j > 0.
and consequently (again by induction) that Kim+j = Kj for all i ≥ 0 and j ≥ 0.