Theorems

Theorem 28   For all $n\in{\bf N}$, $F_{n,q} = q*F_n$.

Done by strong mathematical induction on $n$.

Base Case: $n = 0$ and $n=1$. WTS: $F_{0,q} = q*F_0$ and $F_{1,q} = q*F_1$.

Since $F_0 = F_{0,q} = 0$ and $F_1=1$ and $F_{1,q} = q$, both of these are true.

Induction Step: Assume $F_{n,q} = q*F_n$ and $F_{n-1,q} = q*F_{n-1}$.

WTS: $F_{n+1,q} = q*F_{n+1}$.

We can add the two equations that we know together to get $F_{n,q} + F_{n-1,q} = q*F_n + q*F_{n-1}$, or $F_{n,q} + F_{n-1,q} = q*(F_n + F_{n-1})$. Since $F_{n+1} = F_n + F_{n-1}$ and $F_{n+1,q} = F_{n,q} + F_{n-1,q}$, we can substitute to get $F_{n+1,q} = q*F_{n+1}$, which is what we wanted to show.

Theorem 29   If $\mathbf{q\in{\bf N}}$ and $\mathbf{(q,a) = 1}$, then $\mathbf{t_q (a) = t(a)}$ for all $\mathbf{a\in{\bf N}}$.

We will prove this by showing that $t(a)$ satisfies the definition of $t_q (a)$.

Part 1: WTS: $t(a) > 0$.

This is a property included in the definition of $t(a)$.

Part 2: WTS: $F_{t(a),q}\equiv 0\pmod{a}$.

By the definition of $t(a)$, $F_{t(a)}\equiv 0\pmod{a}$. Thus, by Theorem 28, $F_{t(a),q} = F_{t(a)}*q\equiv 0*q\equiv 0\pmod{a}$, which is what we wanted to show.

Part 3: WTS: $F_{t(a)+1,q}\equiv q\pmod{a}$.

By the definition of $t(a)$, $F_{t(a)+1}\equiv 1\pmod{a}$. Thus, by Theorem 28, $F_{t(a),q} = F_{t(a)}*q\equiv 1*q\equiv q\pmod{a}$, which is what we wanted to show.

Part 4: WTS: If $n\in{\bf N}$ and $n>0$ and $F_{n,q}\equiv 0\pmod{a}$ and $F_{n+1,q}\equiv q\pmod{a}$, then $t(a)\leq n$.

First, note that since $(q,a) = 1$, then by Fact 5, there exists integers $x$ and $y$ such that $qx+ay = 1$, so $qx = 1-ay$, so $qx\equiv 1\pmod{a}$ (by the definition of mod). Now, by Theorem 28, $F_{n,q} = q*F_n$, so, multiplying both sides by $x$, we find that $x*F_{n,q} = x*q*F_n$, or $x*F_{n,q}\equiv F_n\pmod{a}$. Similarly, $x*F_{n+1,q}\equiv F_{n+1}\pmod{a}$. Now, since $F_{n,q}\equiv 0\pmod{a}$, then $x*0\equiv F_n\pmod{a}$, or $F_n\equiv 0\pmod{a}$. Similarly, since $F_{n+1,q}\equiv q\pmod{a}$, then $F_{n+1}\equiv 1\pmod{a}$. Now, by Theorem 9, $t(a)\vert n$, so by Fact 3, $t(a)\leq n$, which is what we wanted to show.

Theorem 30   If $(q,a) = 1$, then $F_{n,q}\equiv 0\pmod{a}$ iff $F_n\equiv 0\pmod{a}$.

Part 1: WTS: If $(q,a) = 1$ and $F_n\equiv 0\pmod{a}$, then $F_{n,q}\equiv 0\pmod{a}$.

By Theorem 28, $F_{n,q} = q*F_n$, so $F_{n,q}\equiv q*F_n\pmod{a}$. Since $F_n\equiv 0\pmod{a}$, then $F_{n,q}\equiv q*0\pmod{a}$, or $F_{n,q}\equiv 0\pmod{a}$, which is what we wanted to show.

Part 2: WTS: If $(q,a) = 1$ and $F_{n,q}\equiv 0\pmod{a}$, then $F_n\equiv 0\pmod{a}$.

By Theorem 28, $F_{n,q} = q*F_n$, so $F_{n,q}\equiv q*F_n\pmod{a}$. Since $F_{n,q}\equiv 0\pmod{a}$, then $q*F_n\equiv 0\pmod{a}$. Since $(q,a) = 1$, by Fact 14 $F_n\equiv 0\pmod{a}$, which is what we wanted to show.

Theorem 31   If $(q,a) = 1$, then $z_q (a) = z(a)$.

We will prove this by showing that $z(a)$ satisfies the properties of $z_q (a)$.

Part 1: WTS: $z(a) > 0$.

This is a property in the definition of $z(a)$.

Part 2: WTS: $F_{z(a),q}\equiv 0\pmod{a}$.

We know that $F_{z(a)}\equiv 0 \pmod{a}$, since this is a property in the definition of $z(a)$. So, since $(q,a) = 1$, by Theorem 30, $F_{z(a),q}\equiv 0\pmod{a}$, which is what we wanted to show.

Part 3: WTS: If $F_{r,q}\equiv 0\pmod{a}$ and $r>0$, then $z(a)\leq r$.

Since $(q,a) = 1$, by Theorem 30, $F_r\equiv 0\pmod{a}$. So, by the definition of $z(a)$, $z(a)\leq r$, which is what we wanted to show.

Theorem 32   $numz(a) = \frac{t(a)}{z(a)}$.

First, note that $\frac{t(a)}{z(a)}$ exists by Theorem 12. Now, since $F_{z(a)}\equiv 0 \pmod{a}$, then $F_{z(a)} = ar$ for some $r\in{\bf N}$. Now, let $k\in{\bf N}$. By Theorem 2, $F_{z(a)}\vert F_{k*z(a)}$, or $ar\vert F_{k*z(a)}$. So, $F_{k*z(a)}\equiv 0\pmod{ar}$, and by Fact 16, $F_{k*z(a)}\equiv 0\pmod{a}$. Thus, every position in the Fibonacci sequence of the form $k*z(a)$ is congruent to $0\pmod{a}$. Also, by Theorem 5, if $F_s\equiv 0\pmod{a}$, where $s\in{\bf N}$, then $z(a)\vert s$, which means that $s$ can be represented in the form $k*z(a)$. Thus, these positions in the Fibonacci sequence are the only ones that are congruent to $0\pmod{a}$. So, now we must count the number between $1$ and $t(a)$. Since they occur every $z(a)$ places, and since $z(a)\vert t(a)$ (by Theorem 12), we conclude that there are $\frac{t(a)}{z(a)}$ such places in the Fibonacci sequence between $1$ and $t(a)$. Thus, $numz(a) = \frac{t(a)}{z(a)}$.

Note that this implies that $numz(a) = {ord}_a b(a)$ by Theorem 13.

Theorem 33   If $(q,a) = 1$, then $numz_q (a) = numz(a)$.

By Theorem 29, $t(a) = t_q (a)$. By Theorem 30, the positions of the zeros in the Fibonacci sequence and the Fibonacci-$q$ sequence are exactly the same, so by the definition of $numz_q (q)$, it follows that $numz_q (a) = numz(a)$.

Theorem 34   $\mathbf{numz(a)\vert\phi(a)}$

This will be proven by a construction. First, write down all Fibonacci-$q$ sequences from the 1st term to the $t_q (a)$ term modulo $a$ such that $(q,a) = 1$ and $1\leq q\leq a-1$. Note that the number of such sequences is just $\phi(a)$. Now, by Theorem 29, each of these sequences is the same length, and by Theorem 30, all terms of value $0$ will be at the same position in every sequence. Now, consider terms whose position is of the form $k*z(a)+1$, where $k\in{\bf N}$ or $k=0$. These terms will be denoted by "$0+$ terms". By Theorem 31, these will all be after the only $0$s in their sequences, and by Theorem 33, there will be the same number of them in each sequence. Now, we start with the first sequence and look at all $0+$ terms in that sequence. Then, we will search for a sequence in which any $0+$ term is equal to any $0+$ term in the first sequence. Now, assume there is a $0+$ term in the $m$th line that is equal to some $0+$ term in the $n$th line. Since all Fibonacci-$q$ sequences are determined by 2 consecutive terms (like the Fibonacci sequence), and all $0+$ terms are preceded by a $0$, we can say that these two sequences are in fact the same sequence shifted by $s*z(a)$ terms, where $s$ is some integer. So, all $0+$ terms in the 2 sequences will be the same. Therefore, we can eliminate or cross out one of these sequences, while still keeping all numbers that were $0+$ terms. Continue this until there are no more duplicate $0+$ terms left. Now, we will show that all $0+$ terms in all Fibonacci-$q$ sequences (where $(q,a) = 1$) are relatively prime to $a$. First, looking back at the proof of Theorem 13, we established that $(F_{z(a)-1},a) = 1$. Since $F_{z(a)-1}\equiv F_{z(a)+1}\pmod{a}$, we can say that $(F_{z(a)+1},a) = 1$. Now, Theorem 7 states that if $F_c\equiv 0\pmod{a}$, then $F_{cr+1}\equiv {(F_{c-1})}^r\pmod{a}$. We can plug in $z(a)$ for $c$ in this formula and notice that $F_{z(a)-1}\equiv F_{z(a)+1}\pmod{a}$ to say that $F_{z(a)*r+1}\equiv {(F_{z(a)+1})}^r\pmod{a}$. Now, since we know that $(F_{z(a)+1},a) = 1$, by Fact 12 we can say that $({(F_{z(a)+1})}^r,a) = 1$ for all $r\in{\bf N}$. We can reduce this to say that $(F_{z(a)*r+1},a) = 1$ for all $r\in{\bf N}$, which says that every $0+$ term in the Fibonacci sequence is relatively prime to $a$. Now, since we are considering every Fibonacci-$q$ sequence such that $(q,a) = 1$, by Fact 11 we can say that $(q*F_{z(a)*r+1},a) = 1$. By Theorem 28, these are just the $0+$ terms in all of the Fibonacci-$q$ sequences, so all $0+$ in every sequence listed are relatively prime to $a$. Notice that every sequence starts with a $0+$ term, and since the first term of every Fibonacci-$q$ sequence is just $q$, we have started with all relatively prime numbers less than $a$. Every time we eliminate a sequence, there is still at least 1 copy left of every number relatively prime to $a$ and less than $a$, since there are 2 copies of the same $0+$ term in each sequence, and only 1 is removed. If there is more than 1 copy left, we eliminate one of the sequences, so after we are finished there is exactly 1 and only 1 copy of every number less than $a$ and relatively prime to $a$. Now, we will count the number of $0+$ terms left in 2 different ways. By the definition of $\phi(a)$, there are exactly $\phi(a)$ $0+$ terms left. Also, since every $0$ in each sequence corresponds to a $0+$ term (the $0$ in the $t_q (a)$ position corresponds to the $0+$ term in the first position), and there are $numz(a)$ $0$s in every sequence, we can say that there are $s*numz(a)$ $0+$ terms, where $s$ is the number of sequences left. So, $s*numz(a) = \phi(a)$, or $numz(a)\vert\phi(a)$ by the definition of divides.