Theorems

Theorem 18   The $k$-Fibonacci sequence is periodic in any modulo for all $\mathbf{k\in{\bf N}}$.

Consider the $k$-Fibonacci sequence in mod $a$: $F_1^k, F_2^k, F_3^k, \ldots$. Now, consider the groups of $k$ consecutive Fibonacci numbers at a time (for example $\{F_1^k, F_2^k,\ldots ,F_k^k\}$, $\{F_2^k, F_3^k,\ldots ,F_{k+1}^k\}$, etc.). Since we are in mod $a$, there are only $a^k$ possible distinct such pairs (since there are $a$ choices for each number, and there are $k$ numbers to choose). If $\{0,0,0,\ldots,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^k-1$ possible distinct pairs. Since the $k$-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^k,F_{n+1}^k,\ldots ,F_{n+k-1}^k\}$ and $\{F_m^k,F_{m+1}^k,\ldots ,F_{m+k-1}^k\}$ are the same (that is, $F_n^k\equiv F_m^k\pmod{a}$ and $F_{n+1}^k\equiv F_{m+1}^k\pmod{a}$, etc.). WLOG (without loss of generality), let $n>m$. Then, we know that $F_{n-1}^k\equiv F_{n+k-1}^k-(F_{n+k-2}^k+F_{n+k-3}^k+\ldots +F_n^k)\pmod{a}$ and $F_{m-1}^k\equiv F_{m+k-1}^k-(F_{m+k-2}^k+F_{m+k-3}^k+\ldots +F_m^k)\pmod{a}$, so $F_{n-1}^k\equiv F_{m-1}^k\pmod{a}$. We can continue this until we find that $F_{n-m-1}^k\equiv F_1^k\pmod{a}$ and $F_{n-m}^k\equiv F_0\pmod{a}$, etc., so $t^k (a)\leq n-m$. So, we can continue this in the other direction and find that the $k$-Fibonacci sequence is periodic.

Theorem 19   If $t\in{\bf N}$ such that for all $i\in{\bf N}$ such that $t-(k-2)\leq i\leq t$, it follows that $F_i^k\equiv 0\pmod{a}$, then $F_{t+n}^k\equiv F_{t-(k-1)}^k*F_n^k\pmod{a}$ for all $n\in{\bf N}$.

Done by strong mathematical induction on $n$.

Base Case: $n=1$. WTS: $F_{t+1}^k\equiv F_{t-(k-1)}^k\pmod{a}$.

By definition, $F_{t+1}^k=\sum_{i=1}^k F_{t+1-i}^k$, and since for all $j\in{\bf N}$ such that $t-k+2\leq j\leq t$, it follows that $F_j^k\equiv 0\pmod{a}$, then $F_{t+1}^k\equiv F_{t-k+1}^k\pmod{a}$, which is what we wanted to show.

Induction Step: Assume $F_{t+i}^k\equiv F_{t-(k-1)}^k*F_i^k\pmod{a}$ for all $i\in{\bf N}$ such that $1\leq i\leq n$.

WTS: $F_{t+n+1}^k\equiv F_{t-(k-1)}^k*F_{n+1}^k\pmod{a}$.

By definition, $F_{t+n+1}^k=\sum_{m=1}^k F_{t+n+1-m}^k$. By hypothesis, $F_{t+n+1}^k\equiv \sum_{m=1}^k F_{t-(k-1)}^k*F_{n+1-m}^k\pmod{a}$. By definition of the $k$-Fibonacci sequence, $F_{t+n+1}^k\equiv F_{t-(k-1)}^k*F_{n+1}^k\pmod{a}$.

Theorem 20   If, for all $i$ between $c-(k-2)$ and $c$, inclusive, then $F_i^k\equiv 0\pmod{a}$, then $F_{cq+1}^k\equiv {(F_{c+1}^k)}^q\pmod{a}$, $\forall q\in{\bf N}$.

Done by weak mathematical induction on $q$.

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

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

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

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

Note that $F_{c(q+1)+1}^k=F_{(cq+1)+c}^k$. Now, since for all $i$ such that $c-(k-2)\leq i\leq c$, it follows that $F_i^k\equiv 0\pmod{a}$, we can apply Theorem 19 to say that $F_{c(q+1)-1}^k\equiv F_{c-(k-1)}^k*F_{cq-1}^k$. Now, $F_{c+1} = \sum_{i=1}^k F_{c-(k-i)}^k\equiv F_{c-(k-1)}^k$, so we can substitute to get $F_{c(q+1)-1}^k\equiv F_{c+1)}^k*F_{cq-1}^k$. By hypothesis, $F_{cq-1}^k\equiv {(F_{c+1}^k)}^q\pmod{a}$, so we can substitute to get $F_{c(q+1)-1}^k\equiv F_{c+1}^k*{(F_{c+1}^k)}^q\pmod{a}$, which means that $F_{c(q+1)-1}^k\equiv {(F_{c-1}^k)}^{q+1}$, which is what we wanted to show.

Theorem 21   $F_{t^k (a)+r}^k\equiv F_r^k\pmod{a}$.

Done by strong mathematical induction on $r$.

Base Case: $r=0$. WTS: $F_{t^k (a)}^k\equiv F_0^k\pmod{a}$.

By definition of $t^k (a)$, this is true.

Induction Step: Assume $F_{t^k (a)+i}^k\equiv F_i^k\pmod{a}$ for all $i\in{\bf N}$ such that $1\leq i\leq r-1$.

WTS: $F_{t^k (a)+r}^k\equiv F_r^k\pmod{a}$.

Since we know the induction step is true for all $i\in{\bf N}$ such that $1\leq i\leq r-1$, we can take the sum of each side as $i$ goes from $n-k$ to $n-1$ to say that $\sum_{i=1}^k F_{t^k(a)+(r-i)}^k \equiv\sum_{i=1}^k F_{r-i}^k\pmod{a}$, which is the same as saying $F_{t^k (a)+r}^k\equiv F_r^k\pmod{a}$ (by definition of the $k$-Fibonacci sequence), which is what we wanted to show.

Theorem 22   If $s\in{\bf N}$, then $F_{t^k (a)*s+r}^k\equiv F_r^k\pmod{a}$.

Done by weak mathematical induction on $s$.

Base Case: $s=1$. WTS: $F_{t^k (a)+r}^k\equiv F_r^k\pmod{a}$.

By Theorem 21, this is true.

Induction Step: Assume $F_{t^k (a)*s+r}^k\equiv F_r^k\pmod{a}$.

WTS: $F_{t^k (a)*(s+1)+r}^k\equiv F_r^k\pmod{a}$.

$F_{t^k (a)*(s+1)+r}^k=F_{t^k (a)*s+t^k (a)+r}^k$ (by arithmetic). So, by assumption, $F_{t^k (a)*s+t^k (a)+r}^k\equiv F_{t^k (a)+r}^k\pmod{a}$, and by transitivity, $F_{t^k (a)*(s+1)+r}^k\equiv F_{t^k (a)+r}^k\pmod{a}$. Now, by Theorem 21, $F_{t^k (a)+r}^k\equiv F_r^k\pmod{a}$, so by transitivity, $F_{t^k (a)*(s+1)+r}\equiv F_r^k\pmod{a}$, which is what we wanted to show.

Note that from this theorem, the corollary that if $r\equiv s\pmod{t^k (a)}$, then $F_r^k\equiv F_s^k\pmod{a}$ follows trivially.

Theorem 23   If for all $i$ between $f-(k-2)$ and $f$, inclusive, it follows that $F_i^k\equiv 0\pmod{a}$, then $z^k (a)\vert f$.

First, divide $f$ by $z^k (a)$ to get $f=z^k (a)*q+r$, where $q,r\in{\bf N}$ and $0\leq r<z^k (a)$. Now, for the sake of contradiction, assume that $r\neq 0$. So, $0<r<z^k (a)$. Now, for all $j\in{\bf Z}$, then $F_{f+j}^k=F_{z^k (a)*q+r+j}^k\equiv F_{z^k (a)-(k-1)}F_{r+j}^k\pmod{a}$ (by Theorem 19). Now, for each $j\in{\bf N}$ such that $r-(k-2)\leq j\leq r$, then $F_j^k\equiv F_{z^k (a)-(k-1)}F_i^k\pmod{a}$ for some $i\in{\bf N}$ such that $f-(k-2)\leq i\leq f$ (since $i=j+z^k (a)*q$). So, $F_j^k\equiv F_{z^k (a)-(k-1)}*0\equiv 0\pmod{a}$. Also, $r>0$ (by assumption). So, by definition of $z^k (a)$, it follows that $r>z^k (a)$. But we already know that $r<z^k (a)$, so this is a contradiction. So, we reject our hypothesis and conclude that $r=0$, so $f=z^k (a)*q$, so $z^k (a)\vert f$.

Theorem 24   If for all $i\in{\bf N}$ such that $f-(k-2)\leq i\leq f$ it follows that $F_i^k\equiv 0\pmod{a}$ and also $F_{f+1}^k\equiv 1\pmod{a}$, then $t^k (a)\vert f$.

First, divide $f$ by $t^k (a)$ to get $f=t^k (a)*q+r$, where $q,r\in{\bf N}$ and $0\leq r<t^k (a)$. Now, for the sake of contradiction, assume that $r\neq 0$. So, $0<r<t^k (a)$. Now, for all $j\in{\bf Z}$, then $F_{f+j}^k=F_{t^k (a)*q+r+j}^k\equiv F_{r+j}^k\pmod{a}$ (by Theorem 22). Now, for each $j\in{\bf N}$ such that $r-(k-2)\leq j\leq r$, then $F_j^k\equiv F_i^k\pmod{a}$ for some $i\in{\bf N}$ such that $f-(k-2)\leq i\leq f$ (since $i=j+t^k (a)*q$). So, $F_j^k\equiv F_i^k\equiv 0\pmod{a}$. Also, $F_{f+1}^k\equiv F_{r+1}^k\equiv 1\pmod{a}$, and $r>0$ (by assumption). So, since $r$ satisfies the definition of $t^k (a)$, it follows that $r>t^k (a)$. But we already know that $r<t^k (a)$, so this is a contradiction. So, we reject our hypothesis and conclude that $r=0$, so $f=t^k (a)*q$, so $t^k (a)\vert f$.

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

$F_c^k\equiv 0\pmod{a}$ and $F_c^k\equiv 0\pmod{b}$, so $F_c^k=ax_0$ and $F_c^k=by_0$ for some $x_0,y_0\in{\bf Z}$. So, $a\vert F_c^k$ and $b\vert F_c^k$, and since $(a,b)=1$, then $ab\vert F_c^k$ (by Fact 8). So, $F_c^k\equiv 0\pmod{ab}$. We can make this same argument to show that for all $i\in{\bf N}$ such that $c-(k-2)\leq i\leq c$, then $F_i^k\equiv 0\pmod{ab}$. Now, since $F_{c+1}^k\equiv 1\pmod{a}$ and $F_{c+1}^k\equiv 1\pmod{b}$, then $F_{c+1}^k=ax_1 +1$ and $F_{c+1}^k=by_1 +1$ for some $x_1,y_1\in{\bf Z}$. So, $a\vert(F_{c+1}^k-1)$ and $b\vert(F_{c+1}^k-1)$, and since $(a,b)=1$, then $ab\vert(F_{c+1}-1)$ (by Fact 8). So, $F_{c+1}\equiv 1\pmod{ab}$. Thus, by Theorem 24, $t^k (ab)=\vert c$.

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

We will prove this by showing that $[t^k (a),t^k (b)]$ satisfies the definition of $t^k (ab)$.

Part 1: WTS: $[t^k (a),t^k (b)]>0$.

By the definition of LCM, $[t^k (a),t^k (b)]>0$.

Part 2: WTS: For all $i$ such that $[t^k (a),t^k (b)]-(k-2)\leq i\leq [t^k (a),t^k (b)], i\in{\bf Z}$, it follows that $F_i^k\equiv 0\pmod{ab}$.

Let $e=[t^k (a),t^k (b)]$, so WTS that for all $i$ such that $e-(k-2)\leq i\leq e, i\in{\bf Z}$, it follows that $F_i^k\equiv 0\pmod{ab}$. Now, since $e=[t^k (a),t^k (b)]$, we know that $e=t^k (a)*q_0$ and $e=t^k (b)*q_1$ for some $q_0,q_1\in{\bf Z}$. Since $e$ and $t^k (a)$ and $t^k (b)$ are positive, we also know that $q_0>0$ and $q_1>0$, so $q_0,q_1\in{\bf N}$. So, by Theorem 22, we can say that for all $g\in{\bf Z}$, $F_{t^k (a)*q_0+g}^k \equiv F_g \equiv F_{t^k (a)+g}^k \pmod{a}$. Similarly, for all $h\in{\bf Z}$, $F_{t^k (b)*q_1+h}^k \equiv F_h \equiv F_{t^k (b)+h}^k \pmod{b}$. Thus, for all $g\in{\bf Z}$, $F_{t^k(a)*q_0+g}^k \equiv F_{t^k (a)+g}^k \pmod{a}$, and for all $h\in{\bf Z}$, $F_{t^k(b)*q_1+h}^k \equiv F_{t^k (b)+h}^k \pmod{b}$. Now, if we let $g$ and $h$ take on all integral values between $-(k-2)$ and $0$ (inclusive), we find that for all $i$ such that $e-(k-2)\leq i\leq e, i\in{\bf Z}$, $F_i^k \equiv F_{t^k (a)+g}^k \pmod{a}$, and $F_i^k \equiv F_{t^k (b)+h}^k \pmod{b}$. Now, since $g$ and $h$ are between $-(k-2)$ and $0$, and by Part 2 of the definition of $t^k$, we can conclude that, for all $i$ such that $[t^k (a),t^k (b)]-(k-2)\leq i\leq [t^k (a),t^k (b)], i\in{\bf Z}$, then $F_i^k\equiv 0\pmod{a}$ and $F_i^k\equiv 0\pmod{b}$. Thus, by Theorem 25, for all $i$ such that $[t^k (a),t^k (b)]-(k-2)\leq i\leq [t^k (a),t^k (b)], i\in{\bf Z}$, then $F_i^k\equiv 0\pmod{ab}$.

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

Since $t^k (a) \vert [t^k (a),t^k (b)]$, then it follows that $[t^k (a),t^k (b)]+1\equiv 1\pmod{a}$. Similarly, $[t^k (a),t^k (b)]+1\equiv 1\pmod{b}$. So, by the corollary to Theorem 22, $F_{[t^k (a),t^k (b)]+1}\equiv 1\pmod{a}$ and $F_{[t^k (a),t^k (b)]+1}\equiv 1\pmod{b}$. Thus, $F_{[t^k (a),t^k (b)+1]}-1\equiv 0\pmod{a}$ and $F_{[t^k (a),t^k (b)+1]} - 1\equiv 0\pmod{b}$, so $a \vert F_{[t^k (a),t^k (b)+1]}-1$ and $b \vert F_{[t^k (a),t^k (b)+1]} - 1$. Since $(a,b)=1$ (which was given), we can use Fact 8 to say that $ab \vert F_{[t^k (a),t^k (b)+1]}-1$. So, $F_{t^k (a),t^k (b)+1]}-1\equiv 0\pmod{ab}$, and thus $F_{t^k (a),t^k (b)+1]}\equiv 1\pmod{ab}$, which is what we wanted to show.

Part 4: WTS: If there exists an $f\in{\bf Z}$ such that for all $i$ such that $f-(k-2)\leq i\leq f, i\in{\bf Z}$, it follows that $F_i^k\equiv 0\pmod{ab}$, and $F_{f+1}*k\equiv 1\pmod{ab}$, then $[t^k (a),t^k (b)]\leq f$.

Since for all $i$ such that $f-(k-2)\leq i\leq f, i\in{\bf Z}$, it follows that $F_i^k\equiv 0\pmod{ab}$, then we can say that for all $i$ such that $f-(k-2)\leq i\leq f, i\in{\bf Z}$, it follows that $F_i^k\equiv 0\pmod{a}$ (by Fact 16. Also, since $F_{f+1}*k\equiv 1\pmod{ab}$, then $F_{f+1}*k\equiv 1\pmod{a}$ (by Fact 16). Thus, by Theorem 24, $t^k (a)\vert f$. Similarly, $t^k (b) \vert f$. So, by the definition of LCM, $[t^k (a), t^k (b)] \vert f$, and by Fact 3, $[t^k (a),t^k (b)]\leq f$, which is what we wanted to show.

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

Let $e=b^k (a)$, so $e=F_{z^k (a)-(k-1)}^k\pmod{a}$ (by definition). Since for all $i$ between $z^k (a)-(k-2)$ and $z^k (a)$, inclusive, $F_i^k\equiv 0\pmod{a}$ (by definition of $z^k (a)$), we know that $e\equiv F_{z^k (a)+1}^k\pmod{a}$. Now, if we find that the first $1$ directly after $k-1$ $0$s is in position number $r$, then $t^k (a)=r-1$, since $F_{(r-1)+1}^k\equiv 1\pmod{a}$ and there are $k-1$ $0$s preceding that term, which satisfies the definition of $t^k (a)$. So, we must examine position numbers $z^k (a)+1,2z^k (a)+1,3z^k (a)+1,\ldots$, since all sequences of $k-1$ $0$s end in position numbers $z^k (a),2z^k (a),3z^k (a),\ldots$ (by Theorem 23). Now, by Theorem 20, $F_{q*z^k (a)+1}^k\equiv {(F_{z^k (a)+1}^k)}^q\pmod{a}$. So, we are looking for the first $q$ such that ${(F_{z^k (a)+1}^k)}^q\equiv 1\pmod{a}$. By definition, this is ${ord}_a (F_{z^k (a)}^k+1)$. So, $t^k (a)=z^k (a)*{ord}_a (b^k (a))+1-1$, or $t^k (a)=z^k (a)*{ord}_a (b^k (a))$.