Theorems

Theorem 1   The Fibonacci sequence is periodic in any modulo.

Consider the Fibonacci sequence in mod $a$: $F_1, F_2, F_3, \ldots$. Now, consider the pairs of consecutive Fibonacci numbers (for example $\{F_1, F_2\}$, $\{F_2, F_3\}$, etc.). Since we are in mod $a$, there are only $a^2$ possible distinct such pairs (since there are $a$ choices for the first number in a pair and $a$ choices for the second number in a pair). If $\{0,0\}$ is one such pair, then the whole sequence must be $0,0,0,0,\ldots$ in mod $a$, which contradicts the initial conditions of the sequence, so there are only $a^2-1$ possible distinct pairs. Since the Fibonacci sequence is infinite, there are an infinite number of pairs, so by the Pigeonhole Principle, at least one of these pairs must repeat. Suppose that the pairs $\{F_n,F_{n+1}\}$ and $\{F_m,F_{m+1}\}$ are the same (that is, $F_n\equiv F_m\pmod{a}$ and $F_{n+1}\equiv F_{m+1}\pmod{a}$). WLOG (without loss of generality), let $n>m$. Then, we know that $F_{n-1}\equiv F_{n+1}-F_n\pmod{a}$ and $F_{m-1}\equiv F_{m+1}-F_m\pmod{a}$, so $F_{n-1}\equiv F_{m-1}\pmod{a}$. We can continue this until we find that $F_{n-m-1}\equiv F_1\pmod{a}$ and $F_{n-m}\equiv F_0\pmod{a}$, so $t(a)\leq n-m$. So, we can continue this in the other direction and find that the Fibonacci sequence is periodic.

Theorem 2   $F_n\vert F_{nk}$, for all $n,k\in{\bf N}$.

Done by weak mathematical induction on $k$.

Base Case: Want To Show(WTS): $F_n\vert F_n$.

Since $F_n=F_n*1$, so $F_n\vert F_n$.

Induction Step: Assume $F_n\vert F_{nk}$, $k\in{\bf N}$.

WTS: $F_n\vert F_{n(k+1)}$.

By the definition of the Fibonacci sequence, we know that $F_{nk+1}=F_{nk}+F_{nk-1}$. So, $F_{nk+2}=F_{nk+1}+F_{nk}=F_{nk}+F_{nk-1}+F_{nk}=2F_{nk}+F_{nk-1}$. Then, $F_{nk+3}=F_{nk+2}+F_{nk+1}=2F_{nk}+F_{nk-1}+F_{nk}+F_{nk-1}= 3F_{nk}+2F_{nk-1}$. Also, $F_{nk+4}=F_{nk+3}+F_{nk+2}=3F_{nk}+2F_{nk-1}+2F_{nk}+F_{nk-1}= 5F_{nk}+3F_{nk-1}$. Notice that the coefficients of $F_{nk}$ and $F_{nk-1}$ are being generated recursively with the same formula as the Fibonacci numbers, so we can say that $F_{nk+j}=F_{nk}*F_{j+1}+F_{nk-1}*F_{j}$ if $j\in{\bf N}$. So, we can substitute $n$ for $j$ to say that $F_{nk+n}=F_{nk}*F_{n+1}+F_{nk-1}*F_{n}$. Now, since we know that $F_n\vert F_{nk}$ (by hypothesis), then $F_{nk}=F_n*c$ for some $c\in{\bf Z}$. So, we can substitute to get $F_{nk+n}=F_n*c*F_{n+1}+F_{nk-1}*F_{n}$. Now, we can factor out an $F_n$ to say $F_{nk+n}=F_n(c*F_{n+1}+F_{nk-1})$. So, by definition of divides, $F_n\vert F_{nk+n}$, and since $nk+n=n(k+1)$, then $F_n\vert F_{n(k+1)}$, which is what we wanted to show.

Theorem 3   If $F_n\equiv 0\pmod{a}$, then $F_{n+t}\equiv F_t*F_{n-1}\pmod{a}$.

Done by strong mathematical induction on $t$.

Base Case: $t=0$ or $t=1$. WTS: $F_{n+t}\equiv F_t*F_{n-1}\pmod{a}$.

For $t=0$, we want to show that $F_n\equiv F_0*F_{n-1}\pmod{a}$. Since we know that $F_n\equiv 0\pmod{a}$ and $F_0=1$ (by definition), so $F_0*F_{n-1}\equiv \pmod{a}$, and $F_n\equiv F_0*F_{n-1}\pmod{a}$. For $t=1$, we want to show that $F_{n+1}\equiv F_1*F_{n-1}$. By the definition of the Fibonacci sequence, $F_{n+1}=F_{n}+F_{n-1}$, so $F_{n+1}\equiv F_{n}+F_{n-1}\pmod{a}$. Since $F_n\equiv 0\pmod{a}$, then $F_{n+1}\equiv F_{n-1}\pmod{a}$. Since $F_1=1$, we can multiply to get that $F_{n+1}\equiv F_1*F_{n-1}\pmod{a}$, which is what we wanted to show.

Induction Step: Assume $F_{n+i}\equiv F_i*F_{n-1}\pmod{a}$, $\forall i\in{\bf Z}$ such that $1\leq i<k$.

WTS: $F_{n+k}\equiv F_k*F_{n-1}\pmod{a}$.

Since $1\leq k-2<k$ and $1\leq k-1<k$, we can say that $F_{n+k-2}\equiv F_{k-2}*F_{n-1}\pmod{a}$ and $F_{n+k-1}\equiv F_{k-1}*F_{n-1}\pmod{a}$. We can add these equations together to say that $F_{n+k-2}+F_{n+k-1}\equiv F_{k-2}*F_{n-1}+F_{k-1}*F_{n-1}\pmod{a}$. Factoring, we get that $F_{n+k-2}+F_{n+k-1}\equiv F_{n-1}(F_{k-2}+F_{k-1})\pmod{a}$. Since $F_{n+k-2}+F_{n+k-1}=F_{n+k}$ and $F_{k-2}+F_{k-1}=F_k$, we can substitute to say that $F_{n+k}\equiv F_k*F_{n-1}$, which is what we wanted to show.

Theorem 4   $(F_n,F_{n-1})=1$.

We will prove this by weak mathematical induction on $n$.

Base Case: $n=1$. WTS: $(F_1,F_2)=1$.

Since $F_1=1$ and $F_2=1$ and $(1,1)=1$, then $(F_1,F_2)=1$, which is what we wanted to show.

Induction Step: Assume $(F_n,F_{n+1})=1$.

WTS: $(F_{n+1},F_{n+2})=1$.

Since $(F_n,F_{n+1})=1$, by Fact 10, $(F_n+F_{n+1},F_{n+1})=1$. So, by the definition of the Fibonacci sequence, $(F_{n+2},F_{n+1})=1$, which is what we wanted to show.

Theorem 5   If $F_n\equiv 0\pmod{a}$, then $z(a)\vert n$.

Let $c=z(a)$. Divide $n$ by $c$ (by Fact 4) to get $n=cq+r$, where $0\leq r<c$. So, $F_n\equiv F_{cq+r}\pmod{a}$. Since $F_n\equiv 0\pmod{a}$, then $F_{cq+r}\equiv 0\pmod{a}$. Since $F_c\equiv 0\pmod{a}$ (by definition of $z(a)$, then $a\vert F_c$, and since $F_c\vert F_{cq}$ (by Theorem 2), then $a\vert F_{cq}$, so $F_{cq}\equiv 0\pmod{a}$. So we can apply Theorem 3 to say that $F_{cq+r}\equiv F_{cq-1}*F_r\pmod{a}$. Since $F_{cq+r}\equiv 0\pmod{a}$, so $0\equiv F_{cq-1}*F_r\pmod{a}$. By Theorem 4, $(F_{cq-1},F_{cq})=1$. Since $F_c\vert F_{cq}$, then by Fact 7, $(F_{cq-1},F_{c})=1$. Since $c=z(a)$, then by definition of $z(a)$, it follows that $F_c\equiv 0\pmod{a}$. So, by Fact 7, $(F_{cq-1},a)=1$. Now, since $0\equiv F_{cq-1}*F_r\pmod{a}$, then by Fact 14, $0\equiv F_r\pmod{a}$. So, if $0<r<c$, then $r$ satisfies the definition of $z(a)$ and is less than $c$, which is a contradiction. So, $r$ must be equal to $0$, so $n=cq$, so $c\vert n$, so $z(a)\vert n$.

Theorem 6   If $\mathbf{(a,b)=1}$, then $\mathbf{z(ab)=[z(a),z(b)]}$.

To show this we are going to show that $[z(a),z(b)]$ satisfies the definition of $z(ab)$.

Part 1: WTS: $F_{[z(a),z(b)]}\equiv 0\pmod{ab}$.

Let $c=z(a)$ and $d=z(b)$ and $e=[c,d]$. Since $e=[c,d]$, then $e=cs_1$ and $e=ds_2$, where $s_1,s_2\in{\bf Z}$ (by definition of LCM). So, $c\vert e$ and $d\vert e$. Also, $F_c\equiv 0\pmod{a}$ and $F_d\equiv 0\pmod{b}$ by definition of $z(a)$ and $z(b)$, so $a\vert F_c$ and $b\vert F_d$. So, by Theorem 2, $a\vert F_e$ and $b\vert F_e$. Since $(a,b)=1$, by Fact 8, $ab\vert F_e$, so $F_e\equiv 0\pmod{ab}$, so $F_{[z(a),z(b)]}\equiv 0\pmod{ab}$, which is what we wanted to show.

Part 2: WTS: If $F_g\equiv 0\pmod{ab}$, then $[z(a),z(b)]\leq g$.

Let $c=z(a)$ and $d=z(b)$ and $e=[c,d]$. Since $e=[c,d]$, then $e=cs_1$ and $e=ds_2$, where $s_1,s_2\in{\bf Z}$ (by definition of LCM). Since $F_g\equiv 0\pmod{ab}$, then $ab\vert F_g$, so $a\vert F_g$ and $b\vert F_g$. So, $F_g\equiv 0\pmod{a}$ and $F_g\equiv 0\pmod{b}$. Now, by Theorem 5, $c\vert F_g$ and $d\vert F_g$. So, by definition of LCM, $[c,d]\vert F_g$, so $[c,d]\leq F_g$ (by Theorem 3). So, $[z(a),z(b)]\leq F_g$, which is what we wanted to show, so we are done.

Theorem 7   If $F_c\equiv 0\pmod{a}$, then $F_{cq-1}\equiv {(F_{c-1})}^q\pmod{a}$, $\forall q\in{\bf N}$.

Done by weak mathematical induction on $q$.

Base Case: $q=1$. WTS: $F_{c-1}\equiv {(F_{c-1})}^1\pmod{a}$.

Since $F_{c-1}\equiv F_{c-1}\pmod{a}$, then $F_{c-1}\equiv {(F_{c-1})}^1\pmod{a}$, which is what we wanted to show.

Induction Step: Assume $F_{cq-1}\equiv {(F_{c-1})}^q\pmod{a}$.

WTS: $F_{c(q+1)-1}\equiv {(F_{c-1})}^{q+1}\pmod{a}$.

Note that $F_{c(q+1)-1}=F_{(cq-1)+c}$. Now, since $F_c\equiv 0\pmod{a}$, we can apply Theorem 3 to say that $F_{c(q+1)-1}\equiv F_{c-1}*F_{cq-1}$. By hypothesis, $F_{cq-1}\equiv {(F_{c-1})}^q\pmod{a}$, so we can substitute to get $F_{c(q+1)-1}\equiv F_{c-1}*{(F_{c-1})}^q\pmod{a}$, which means that $F_{c(q+1)-1}\equiv {(F_{c-1})}^{q+1}$, which is what we wanted to show.

Theorem 8   $F_{t(a)*q+r}\equiv F_r\pmod{a}$

Since $F_{t(a)+1}\equiv F_{t(a)}+F_{t(a)-1}\pmod{a}$, then $F_{t(a)-1}\equiv F_{t(a)+1}-F_{t(a)}\pmod{a}$. Since $F_{t(a)}\equiv 0\pmod{a}$ and $F_{t(a)+1}\equiv 1\pmod{a}$ (by definition of $t(a)$), then $F_{t(a)-1}\equiv 1\pmod{a}$. Now, by Theorem 7, $F_{t(a)*q-1}\equiv {(F_{t(a)-1})}^q\pmod{a}$ (since $F_{t(a)}\equiv 0\pmod{a}$). Also, $F_{t(a)*q+r}\equiv F_{t(a)*q-1}*F_r\pmod{a}$ by Theorem 3. So, we can substitute to say that $F_{t(a)*q+r}\equiv 1*F_r\pmod{a}$, so $F_{t(a)*q+r}\equiv F_r\pmod{a}$, which is what we wanted to show.

Theorem 9   If $F_k\equiv 0\pmod{a}$ and $F_{k+1}\equiv 1\pmod{a}$, then $t(a)\vert k$.

Let $c=t(a)$. Divide $k$ by $c$ to get $k=cq+b$, where $q,b\in{\bf Z}$ and $0\leq b <c$. Since $F_k\equiv 0\pmod{a}$, then $F_{cq+b}\equiv 0\pmod{a}$, so $F_b\equiv 0\pmod{a}$ (by Theorem 8). Since $F_{k+1}\equiv 1\pmod{a}$, then $F_{cq+b+1}\equiv 1\pmod{a}$, so $F_{b+1}\equiv 1\pmod{a}$ (by Theorem 8). If $0<b<c$, then $b$ satisfies the definition of $t(a)$, but is smaller than $t(a)$ (since $c=t(a)$), which is a contradiction. So, $b=0$, and $k=cq$, so $t(a)\vert k$.

Theorem 10   If $t(a)\vert c$ and $t(b)\vert c$ and $(a,b)=1$, then $t(ab)\vert c$.

$F_c\equiv 0\pmod{a}$ and $F_c\equiv 0\pmod{b}$, so $F_c=ax_0$ and $F_c=by_0$ for some $x_0,y_0\in{\bf Z}$. So, $a\vert F_c$ and $b\vert F_c$, and since $(a,b)=1$, then $ab\vert F_c$ (by Fact 8). So, $F_c\equiv 0\pmod{ab}$. Now, since $F_{c+1}\equiv 1\pmod{a}$ and $F_{c+1}\equiv 1\pmod{b}$, then $F_{c+1}=ax_1 +1$ and $F_{c+1}=by_1 +1$ for some $x_1,y_1\in{\bf Z}$. So, $a\vert(F_{c+1}-1)$ and $b\vert(F_{c+1}-1)$, and since $(a,b)=1$, then $ab\vert(F_{c+1}-1)$ (by Fact 8). So, $F_{c+1}\equiv 1\pmod{ab}$. By Theorem 9, $t(ab)\vert c$.

Theorem 11   If $\mathbf{(a,b)=1}$, then $\mathbf{t(ab)=[t(a),t(b)]}$.

We will show this by showing that $t(ab)\vert[t(a),t(b)]$ and $[t(a),t(b)]\vert t(ab)$. $t(a)\vert[t(a),t(b)]$ and $t(b)\vert[t(a),t(b)]$ (by definition of LCM), and since $(a,b)=1$, then $t(ab)\vert[t(a),t(b)]$ (by Theorem 10). $F_{t(ab)}\equiv 0\pmod{ab}$ and $F_{t(ab)+1}\equiv 1\pmod{ab}$, so $F_{t(ab)}\equiv 0\pmod{a}$ and $F_{t(ab)+1}\equiv 1\pmod{a}$ by Fact 16, so by Theorem 9, $t(a)\vert t(ab)$. Since $F_{t(ab)}\equiv 0\pmod{ab}$ and $F_{t(ab)+1}\equiv 1\pmod{ab}$, so $F_{t(ab)}\equiv 0\pmod{b}$ and $F_{t(ab)+1}\equiv 1\pmod{b}$ by Fact 16, so by Theorem 9, $t(b)\vert t(ab)$. So, by definition of LCM, $[t(a),t(b)]\vert t(ab)$. Since $t(ab)>0$ and $[t(a),t(b)]>0$, by Fact 15, $t(ab)=[t(a),t(b)]$.

Theorem 12   $z(a)\vert t(a)$.

$F_{t(a)}\equiv 0\pmod{a}$ by definition of $t(a)$, so $z(a)\vert t(a)$ by Theorem 5.

Theorem 13   $\mathbf{t(a)=z(a)*{ord}_a (b(a))}$

Let $e=b(a)$, so $e=F_{z(a)-1}$ (by definition). By Theorem 4, $(e,F_{z(a)})=1$, so $(e,aq)=1$ for some $q\in{\bf Z}$, so by Theorem 7, $(e,a)=1$. Therefore, ${ord}_a (e)$ exists, so ${ord}_a (b(a))$ exists. Now, if we find that the first $1$ directly before a $0$ is in position number $k$, then $t(a)=k+1$, since $F_{k+1}\equiv 0\pmod{a}$ and $F_{k+2}\equiv F_k+F_{k+1}\equiv 1\pmod{a}$. So, we must examine position numbers $z(a)-1,2z(a)-1,3z(a)-1,\ldots$, since all zeroes are in position numbers $z(a),2z(a),3z(a),\ldots$ (by Theorem 5). Now, by Theorem 7, $F_{q*z(a)-1}\equiv {(F_{z(a)-1})}^q\pmod{a}$ (since $F_{z(a)}\equiv 0 \pmod{a}$ by definition of $z(a)$). So, we are looking for the first $q$ such that ${(F_{z(a)-1})}^q\equiv 1\pmod{a}$. By definition, this is ${ord}_a (F_{z(a)}-1)$. So, $t(a)=z(a)*{ord}_a (b(a))-1+1$, or $t(a)=z(a)*{ord}_a (b(a))$.

Theorem 14   $F_{n-2}F_{n+2}=F_{n-1}F_{n+1}+2*{(-1)}^{n+1}$ for all $n\in{\bf N}, n>1$.

Done by weak mathematical induction on $n$.

Base Case: $n=2$. WTS: $F_0F_4=F_1F_3+2*{(-1)}^3$

Since $F_0=0$, $F_4=3$, $F_1=1$, $F_3=2$, and ${(-1)}^3=-1$, and $1*2+2*-1=0$, we conclude that the theorem is true for $n=2$.

Induction Step: Assume $F_{n-2}F_{n+2}=F_{n-1}F_{n+1}+2*{(-1)}^{n+1}$.

WTS: $F_{n-1}F_{n+3}=F_nF_{n+2}+2*{(-1)}^{n+2}$.

We can rearrange our assumption to say that $F_{n-1}F_{n+1}=F_{n-2}F_{n+2}-2*{(-1)}^{n+1}$, which is the same thing as $F_{n-1}F_{n+1}=F_{n-2}F_{n+2}+2*{(-1)}^{n+2}$. We can add $F_{n-1}F_{n+2}$ to both sides to get $F_{n-1}F_{n+1}+F_{n-1}F_{n+2}=F_{n-1}F_{n+2}+F_{n-2}F_{n+2}+2*{(-1)}^{n+2}$ and factor to get $F_{n-1}({F_{n+1}+F_{n+2}})=F_{n+2}({F_{n-1}+F_{n-2}})+2*{(-1)^{n+2}}$ and simplify to say that $F_{n-1}F_{n+3}=F_{n+2}F_n+2*{(-1)}^{n+2}$, which is what we wanted to show.

Theorem 15   ${({F_n})}^2=F_{n-1}F_{n+1}+{(-1)}^{n+1}$ for all $n\in{\bf N}, n>1$.

Done by weak mathematical induction on $n$.

Base Case: $n=2$. WTS: ${({F_2})}^2=F_1F_3+{(-1)}^3$.

Since $F_2=1$, $F_1=1$, $F_3=2$, and ${(-1)}^3=-1$, and $1^2=1*2-1$, we conclude that the theorem is true for $n=2$.

Induction Step: Assume ${({F_n})}^2=F_{n-1}F_{n+1}+{(-1)}^{n+1}$.

WTS: ${({F_{n+1}})}^2=F_nF_{n+2}+{(-1)}^{n+2}$.

We can add ${({F_{n-1}})}^2+2F_{n-1}F_n$ to both sides to find that ${({F_n})}^2+{({F_{n-1}})}^2+2F_{n-1}F_n=F_{n-1}F_{n+1}+{({F_{n-1}})}^2+2F_{n-1}F_n+{(-1)}^{n+1}$, or ${({F_n+F_{n-1}})}^2=F_{n-1}({F_{n+1}+F_{n-1}+2F_n})+{(-1)}^{n+1}$, which is the same as ${({F_{n+1}})}^2=F_{n-1}F_{n+3}+{(-1)}^{n+1}$. By Theorem 14, this reduces to ${({F_{n+1}})}^2=F_nF_{n+2}+2*{(-1)}^{n+2}+{(-1)}^{n+1}$, which is the same as ${({F_{n+1}})}^2=F_nF_{n+2}+{(-1)}^{n+2}$, which is what we wanted to show.

Theorem 16   ${ord}_{F_n} (F_{n-1})=3+{(-1)}^{n+1}$, for all $n\in{\bf N}, n>3$.

First, $(F_{n-1},F_n)=1$ by Theorem 4, so ${ord}_{F_n} (F_{n-1})$ exists. By Theorem 15, ${({F_{n-1}})}^2=F_{n-2}F_n+{(-1)}^n$, so ${({F_{n-1}})}^2\equiv {(-1)}^n\pmod{F_n}$. If $n$ is even, then ${(F_{n-1})}^2\equiv 1\pmod{F_n}$, so ${ord}_{F_n} (F_{n-1})=2=3+{(-1)}^{n+1}$. If $n$ is odd, then ${(F_{n-1})}^2\equiv -1\pmod{F_n}$, so ${(F_{n-1})}^4\equiv 1\pmod{F_n}$, so ${ord}_{F_n} (F_{n-1})=4=3+{(-1)}^{n+1}$.

Theorem 17   $\mathbf{t({F_n})=n*({3+{(-1)}^{n+1}})}$, for all $\mathbf{n\in{\bf N}, n>3}$.

First, we notice that $z({F_n})=n$, since $F_n\equiv 0\pmod{F_n}$ and all Fibonacci numbers before this are less than $F_n$, so they cannot be congruent to $0\pmod{F_n}$. So, $b({F_n})=F_{n-1}$. Now, since ${ord}_{F_n} (F_{n-1})=3+{(-1)}^{n+1}$ (by Theorem 16), then we can apply Theorem 13 to say that $t({F_n})=z({F_n})*{ord}_{F_n} (F_{n-1})=n*({3+{(-1)}^{n+1}})$.