Theorems

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

Done by strong mathematical induction on $n$.

Base Case: $2-k\leq n\leq 1$. WTS: $F_{n,q}^k = q*F_n^k$.

If $2-k\leq n\leq 0$, then $F_{n,q}^k=0$ and $F_n^k=0$. Otherwise, $n=1$, so $F_{n,q}^k = q$ and $F_n^k = 1$, so all cases are true.

Induction Step: Assume for all $1\leq i\leq k$, that $F_{n-i,q}^k = q*F_{n-i}^k$.

WTS: $F_{n,q}^k = q*F_{n}^k$.

We can add the given from $i = 1$ to $i = k$ to get that $\sum_{i=1}^k F_{n-i,q}^k = \sum_{i=1}^k q*F_{n-i}^k$, or that $\sum_{i=1}^k F_{n-i,q}^k = q*\sum_{i=1}^k F_{n-i}^k$. By the definition of the sequences, these collapse to $F_{n,q}^k = q*F_n^k$, which is what we wanted to show.

Theorem 36   If $\mathbf{q\in{\bf N}}$ and $\mathbf{(q,a) = 1}$, then $\mathbf{t^k_q (a) = t^k (a)}$ for all $\mathbf{a\in{\bf N}}$.

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

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

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

Part 2: WTS: For all $i$ between $t^k (a)-(k-2)$ and $t^k (a)$, inclusive, $F_{i,q}^k\equiv 0\pmod{a}$.

Let $i$ be between $t^k (a)-(k-2)$ and $t^k (a)$, inclusive. By the definition of $t^k (a)$, $F_{i,q}^k\equiv 0\pmod{a}$. Thus, by Theorem 35, $F_{i,q}^k = F_i^k*q\equiv 0*q\equiv 0\pmod{a}$ (since $F_i^k\equiv 0\pmod{a}$ by definition of $t^k (a)$), which is what we wanted to show.

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

By the definition of $t^k (a)$, $F_{t^k (a)+1}^k\equiv 1\pmod{a}$. Thus, by Theorem 35, $F_{t^k (a),q}^k = F_{t^k (a)}^k*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 for all $i$ such that $n-(k-2)\leq i\leq n$, it follows that $F_{i,q}^k\equiv 0\pmod{a}$ and also $F_{n+1,q}^k\equiv q\pmod{a}$, then $t^k (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, let $n-(k-2)\leq i\leq n$, so by Theorem 28, $F_{i,q}^k = q*F_i^k$, so, multiplying both sides by $x$, we find that $x*F_{i,q}^k = x*q*F_i^k$, or $x*F_{i,q}^k\equiv F_i^k\pmod{a}$. Now, since $F_{i,q}^k\equiv 0\pmod{a}$, then $x*0\equiv F_i^k\pmod{a}$, or $F_i^k\equiv 0\pmod{a}$. Similarly, $x*F_{n+1,q}^k\equiv F_{n+1}^k\pmod{a}$, and $F_{n+1}^k\equiv 1\pmod{a}$. Now by Theorem 24, $t^k (a)\vert n$, so by Fact 3, $t^k (a)\leq n$, which is what we wanted to show.

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

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

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

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

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

Theorem 38   If $(q,a) = 1$, then $z^k_q (a) = z^k (a)$.

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

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

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

Part 2: WTS: For all $i$ between $z^k (a)-(k-2)$ and $z^k (a)$, inclusive, $F_{i,q}^k\equiv 0\pmod{a}$.

Let $i$ be between $z^k (a)-(k-2)$ and $z^k (a)$, inclusive. We know that $F_i^k\equiv 0\pmod{a}$, since this is a property in the definition of $z^k (a)$. So, since $(q,a) = 1$, by Theorem 37, $F_{i,q}\equiv 0\pmod{a}$, which is what we wanted to show.

Part 3: WTS: If, for all $i$ between $r-(k-2)$ and $r$, inclusive, it follows that $F_{i,q}\equiv 0\pmod{a}$ and $r>0$, then $z^k (a)\leq r$.

Let $i$ be between $r-(k-2)$ and $r$, inclusive. Since $(q,a) = 1$, by Theorem 37, $F_i\equiv 0\pmod{a}$. So, this is true for all $i$ between $r-(k-2)$ and $r$, so by the definition of $z^k (a)$, it follows that $z^k (a)\leq r$, which is what we wanted to show.

Theorem 39   If $(q,a) = 1$, then $numz^k_q (a) = numz^k (a)$.

By Theorem 36, $t^k (a) = t^k_q (a)$. By Theorem 37, the positions of the zeros in the $k$-Fibonacci sequence and the $k$-Fibonacci-$q$ sequence are exactly the same, so by the definition of $numz^k_q (q)$, it follows that $numz^k_q (a) = numz^k (a)$.

Theorem 40   $\mathbf{numz^k (a)\vert\phi(a)}$

This will be proven by a construction. First, write down all $k$-Fibonacci-$q$ sequences from the 1st term to the $t^k_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 36, each of these sequences is the same length, and by Theorem 37, all positions that have $k-1$ consecutive $0$s will start at the same position in every sequence. Now, consider terms whose position is of the form $r*z^k (a)+1$, where $r\in{\bf N}$ or $r=0$. These terms will be denoted by "$0+^k$ terms". By Theorem 38, these will all be after the only places that have $k-1$ consecutive $0$s in their sequences, and by Theorem 39, there will be the same number of $0+^k$ terms in each sequence. Now, we start with the first sequence and look at all $0+^k$ terms in that sequence. Then, we will search for a sequence in which any $0+^k$ term is equal to any $0+^k$ term in the first sequence. Now, assume there is a $0+^k$ term in the $m$th line that is equal to some $0+^k$ term in the $n$th line. Since all $k$-Fibonacci-$q$ sequences are determined by $k$ consecutive terms (like the $k$-Fibonacci sequence), and all $0+^k$ terms are preceded by $k-1$ $0$s, we can say that these two sequences are in fact the same sequence shifted by $s*z^k (a)$ terms, where $s$ is some integer. So, all $0+^k$ terms in the sequences will be the same. Therefore, we can eliminate or cross out one of these sequences, while still keeping all numbers that were $0+^k$ terms. Continue this until there are no more duplicate $0+^k$ terms left. Now, we will show that all $0+^k$ terms in all $k$-Fibonacci-$q$ sequences (where $(q,a) = 1$) are relatively prime to $a$. First, looking back at the proof of Theorem 27, we established that $(F_{z^k (a)+1}^k,a) = 1$ (since ${ord}_a F_{z^k (a)+1}^k$ exists). Now, Theorem 20 states that if, for all $i$ between $c-(k-2)$ and $c$, inclusive, it follows that $F_i^k\equiv 0\pmod{a}$, then $F_{cr+1}^k\equiv {(F_{c-1}^k)}^r\pmod{a}$. We can plug in $z^k (a)$ for $c$ in this formula to say that $F_{z^k (a)*r+1}^k\equiv {(F_{z^k (a)+1}^k)}^r\pmod{a}$. Now, since we know that $(F_{z^k (a)+1}^k,a) = 1$, by Fact 12 we can say that $({(F_{z^k (a)+1}^k)}^r,a) = 1$ for all $r\in{\bf N}$. We can reduce this to say that $(F_{z^k (a)*r+1}^k,a) = 1$ for all $r\in{\bf N}$, which says that every $0+^k$ term in the $k$-Fibonacci sequence is relatively prime to $a$. Now, since we are considering every $k$-Fibonacci-$q$ sequence such that $(q,a) = 1$, by Fact 11 we can say that $(q*F_{z^k (a)*r+1}^k,a) = 1$. By Theorem 35, these are just the $0+^k$ terms in all of the $k$-Fibonacci-$q$ sequences, so all $0+^k$ terms in every sequence listed are relatively prime to $a$. Notice that every sequence starts with a $0+^k$ term, and since the first term of every $k$-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+^k$ 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+^k$ terms left in 2 different ways. By the definition of $\phi(a)$, there are exactly $\phi(a)$ $0+^k$ terms left. Also, since every sequence of $k-1$ consecutive $0$s in each sequence corresponds to a $0+^k$ term (the $0$s ending in the $t_q^k (a)$ position correspond to the $0+^k$ term in the first position), and there are $numz^k (a)$ sequences of $k-1$ consecutive $0$s in every sequence, we can say that there are $s*numz^k (a)$ $0+^k$ terms, where $s$ is the number of sequences left. So, $s*numz^k (a) = \phi(a)$, or $numz^k (a)\vert\phi(a)$ by the definition of divides.