Theorems

Crucial Note: In this section, we will only consider ${^a _b}F_n\pmod{m}$ such that $(a,m)=1$ and $(b,m)=1$ - otherwise, ${^a _b}z(m)$ and ${^a _b}t(m)$ are not guaranteed to exist.

Theorem 41   The generalized $a,b$-Fibonacci numbers are periodic in any modulo.

Consider the generalized $a,b$-Fibonacci sequence in mod $m$: ${^a _b}F_1, {^a _b}F_2, {^a _b}F_3, \ldots$. Now, consider the pairs of consecutive generalized $a,b$-Fibonacci numbers (for example $\{{^a _b}F_1, {^a _b}F_2\}$, $\{{^a _b}F_2, {^a _b}F_3\}$, etc.). Since we are in mod $m$, there are only $m^2$ possible distinct such pairs (since there are $m$ choices for the first number in a pair and $m$ 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 $m$, which contradicts the initial conditions of the sequence, so there are only $m^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 $\{{^a _b}F_n,{^a _b}F_{n+1}\}$ and $\{{^a _b}F_r,{^a _b}F_{r+1}\}$ are the same (that is, ${^a _b}F_n\equiv {^a _b}F_r\pmod{m}$ and ${^a _b}F_{n+1}\equiv {^a _b}F_{r+1}\pmod{m}$). WLOG (without loss of generality), let $n>r$. Then, we know that $b*{^a _b}F_{n-1}\equiv {^a _b}F_{n+1}-a*{^a _b}F_n\pmod{m}$ (and since $(b,m)=1$, ${^a _b}F_{n-1}$ has a unique solution) and $b*{^a _b}F_{r-1}\equiv a*{^a _b}F_{r+1}-{^a _b}F_r\pmod{m}$ (and since $(b,m)=1$, ${^a _b}F_{r-1}$ has a unique solution), so $F_{n-1}\equiv F_{r-1}\pmod{m}$. We can continue this until we find that ${^a _b}F_{n-r-1}\equiv {^a _b}F_1\pmod{m}$ and ${^a _b}F_{n-r}\equiv {^a _b}F_0\pmod{m}$, so $t(m)\leq n-r$. So, we can continue this in the other direction and find that the generalized $a,b$-Fibonacci sequence is periodic.

Theorem 42   If ${^a _b}F_n\equiv 0\pmod{m}$, then ${^a _b}F_{n+t}\equiv b*{^a _b}F_t*{^a _b}F_{n-1}\pmod{m}$.

Done by strong mathematical induction on $t$.

Base Case: $t=1$. WTS: ${^a _b}F_{n+1}=b*{^a _b}F_1*{^a _b}F_{n-1}\pmod{m}$.

By the definition of the Fibonacci sequence, ${^a _b}F_{n+1}=a*{^a _b}F_{n}+b*{^a _b}F_{n-1}$, so ${^a _b}F_{n+1}\equiv a*{^a _b}F_{n}+b*{^a _b}F_{n-1}\pmod{m}$. Since ${^a _b}F_n\equiv 0\pmod{m}$, then ${^a _b}F_{n+1}\equiv b*{^a _b}F_{n-1}\pmod{m}$. Since ${^a _b}F_1 = 1$, we can multiply to get that ${^a _b}F_{n+1}\equiv b*{^a _b}F_1*{^a _b}F_{n-1}\pmod{m}$, which is what we wanted to show.

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

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

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

Theorem 43   If ${^a _b}z(m)\vert n$, then ${^a _b}F_n\equiv 0\pmod{m}$.

Let $q$ be the integer such that ${^a _b}z(m)*q=n$ (this is guaranteed to exist by the definition of divides). Now we will use weak mathematical induction on $q$.

Base Case: $q=1$. WTS: ${^a _b}F_{{^a _b}z(m)}\equiv 0\pmod{m}$.

This follows from the definition of ${^a _b}z(m)$.

Induction Step: Assume ${^a _b}F_{q*{^a _b}z(m)}\equiv 0\pmod{m}$.

WTS: ${^a _b}F_{(q+1)*{^a _b}z(m)}\equiv 0\pmod{m}$.

Since ${^a _b}F_{q*{^a _b}z(m)}\equiv 0\pmod{m}$ (given), we can apply Theorem 42 to say that ${^a _b}F_{q*{^a _b}z(m)+{^a _b}z(m)}\equiv b*{^a _b}F_{{^a _b}z(m)}* {^a _b}F_{q*{^a _b}z(m)-1}\pmod{m}$. Since ${^a _b}F_{{^a _b}z(m)}\equiv 0\pmod{m}$ (by the definition of ${^a _b}z(m)$, we can say that ${^a _b}F_{q*{^a _b}z(m)+{^a _b}z(m)}\equiv 0\pmod{m}$. Simplifying, we get that ${^a _b}F_{(q+1)*{^a _b}z(m)}\equiv 0\pmod{m}$, which is what we wanted to show.

Theorem 44   If ${^a _b}F_n\equiv 0\pmod{m}$, then ${^a _b}z(m)\vert n$.

Let $c={^a _b}z(m)$. Divide $n$ by $c$ to get $n=cq+r$, where $0\leq r<c$. So, ${^a _b}F_n\equiv {^a _b}F_{cq+r}\pmod{m}$. Since ${^a _b}F_n\equiv 0\pmod{m}$, then ${^a _b}F_{cq+r}\equiv 0\pmod{m}$. By Theorem 43, ${^a _b}F_{cq}\equiv 0\pmod{m}$. So we can apply Theorem 42 to say that ${^a _b}F_{cq+r}\equiv b*{^a _b}F_r*{^a _b}F_{cq-1}\pmod{m}$. Now, since ${^a _b}F_{cq+r}\equiv 0\pmod{m}$, we can say that $b*{^a _b}F_r*{^a _b}F_{cq-1}\equiv 0\pmod{m}$. Since $(b,m)=1$, by Fact 14 we know that ${^a _b}F_r*{^a _b}F_{cq-1}\equiv 0\pmod{m}$. Now, assume for the sake of contradiction that $({^a _b}F_{cq-1},m)=d$, where $d\in{\bf Z}$ and $d\neq 1$. So, $d\vert m$ and $d\vert{^a _b}F_{cq-1}$. Now, since ${^a _b}F_{cq}\equiv 0\pmod{m}$ (by Theorem 43), then $m\vert{^a _b}F_{cq}$, and since $d\vert m$, then $d\vert{^a _b}F_{cq}$. Now, we notice that $d$ divides 2 consecutive terms of the generalized $a,b$-Fibonacci sequence, and since this sequence is determined by 2 consecutive terms, all terms past these 2 in the sequence must be divisible by $d$. Now, consider the $s$th term, where $s>cq$. So, by the previous argument, $d\vert{^a _b}F_s$. So, $({^a _b}F_s,m)\geq d$, since $d$ is a common factor, and since $d>1$, then $({^a _b}F_s,m)>1$, or $({^a _b}F_s,m)\neq 1$. Now, we can take the contrapositive of Fact 6 to say that if $({^a _b}F_s,m)$ does not divide $1$, then there do not exist integers $x$ and $y$ such that ${^a _b}F_s*x + m*y =1$, so we know that there do not exist integers $x$ and $y$ such that ${^a _b}F_s*x + m*y =1$, so ${^a _b}F_s$ is not congruent to $1\pmod{m}$. Now we have shown this for all $s$ such that $s>cq$ - but this is a contradiction to the fact that the generalized $a,b$-Fibonacci sequence is periodic! So, we reject our hypothesis, and conclude that $({^a _b}F_{cq-1},m)=1$. Then, by Fact 14, ${^a _b}F_r\equiv 0\pmod{m}$. Now, we know that $0\leq r<c$. If $0<r<c$, then we have a contradiction to the definition of $z(a)$ (since $r<z(a)$, but satisfies the definition of $z(a)$). Thus, we reject that case, and conclude that $r=0$. Thus, $n=cq$, which means that $c\vert n$, or ${^a _b}z(m)\vert n$.

Theorem 45   If ${^a _b}F_c\equiv 0\pmod{m}$, then ${^a _b}F_{cq+1}\equiv {(b*{^a _b}F_{c-1})}^q\pmod{m}$, $\forall q\in{\bf N}$.

Done by weak mathematical induction on $q$.

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

Since ${^a _b}F_{c+1}=a*{^a _b}F_c+b*{^a _b}F_{c-1}$, then since ${^a _b}F_c\equiv 0\pmod{m}$, we know that ${^a _b}F_{c+1}\equiv b*{^a _b}F_{c-1}\pmod{m}$, or ${^a _b}F_{c+1}\equiv {(b*{^a _b}F_{c-1})}^1\pmod{m}$, which is what we wanted to show.

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

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

Note that ${^a _b}F_{c(q+1)+1}={^a _b}F_{c+(cq+1)}$. Now, since ${^a _b}F_c\equiv 0\pmod{m}$, we know by Theorem 42 that ${^a _b}F_{c(q+1)+1}\equiv b*{^a _b}F_{c-1}*{^a _b}F_{cq+1}$. Now, by the given, ${^a _b}F_{cq+1}\equiv {(b*{^a _b}F_{c-1})}^q\pmod{m}$, so we can substitute to get ${^a _b}F_{c(q+1)+1}\equiv b*{^a _b}F_{c-1}*{(b*{^a _b}F_{c-1})}^q\pmod{m}$. We can simplify this to say that ${^a _b}F_{c(q+1)+1}\equiv {(b*{^a _b}F_{c-1})}^{q+1}\pmod{m}$, which is what we wanted to show.

Theorem 46   $F_{{^a _b}t(m)*q+r}\equiv F_r\pmod{m}$

Since ${^a _b}F_{{^a _b}t(m)+1}\equiv a*{^a _b}F_{{^a _b}t(m)}+b*{^a _b}F_{{^a _b}t(m)-1}\pmod{m}$, then $b*{^a _b}F_{{^a _b}t(m)-1}\equiv {^a _b}F_{{^a _b}t(m)+1}-a*{^a _b}F_{{^a _b}t(m)}\pmod{m}$. If we let $x$ be an integer such that $x*b\equiv 1\pmod{m}$ ($x$ exists by the fact that $(b,m)=1$ and Fact 13), then we can say that ${^a _b}F_{{^a _b}t(m)-1}\equiv x*({^a _b}F_{{^a _b}t(m)+1}-a*{^a _b}F_{{^a _b}t(m)})\pmod{m}$. Since ${^a _b}F_{{^a _b}t(m)}\equiv 0\pmod{m}$ (by definition of ${^a _b}t(m)$ we can simplify this to ${^a _b}F_{{^a _b}t(m)-1}\equiv x*({^a _b}F_{{^a _b}t(m)+1}\pmod{m}$. We know that ${^a _b}F_{{^a _b}t(m)+1}\equiv 1\pmod{m}$ by the definition of ${^a _b}t(m)$, so we can substitute to say that ${^a _b}F_{{^a _b}t(m)-1}\equiv x\pmod{m}$. Now, by Theorem 45, ${^a _b}F_{{^a _b}t(m)*q+1}\equiv {(b*{^a _b}F_{{^a _b}t(m)-1})}^q\pmod{m}$ (since ${^a _b}F_{{^a _b}t(m)}\equiv 0\pmod{m}$), which means that ${^a _b}F_{{^a _b}t(m)*q+1}\equiv {(b*x)}^q\pmod{m}$, or ${^a _b}F_{{^a _b}t(m)*q+1}\equiv 1\pmod{m}$. Now, we can work backwards using the ideas from the preceding steps to determine that ${^a _b}F_{{^a _b}t(m)*q-1}\equiv x\pmod{m}$. Also, ${^a _b}F_{{^a _b}t(m)*q+r}\equiv b*{^a _b}F_{{^a _b}t(m)*q-1}*{^a _b}F_r\pmod{m}$ by Theorem 42. So, we can substitute to say that ${^a _b}F_{{^a _b}t(m)*q+r}\equiv b*x*{^a _b}F_r\pmod{m}$, and since we defined $x$ such that $x*b\equiv 1\pmod{m}$, we conclude that ${^a _b}F_{{^a _b}t(m)*q+r}\equiv {^a _b}F_r\pmod{m}$, which is what we wanted to show.

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

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

Theorem 48   If ${^a _b}t(x)\vert c$ and ${^a _b}t(x)\vert c$ and $(x,y)=1$, then ${^a _b}t(xy)\vert c$.

${^a _b}F_c\equiv 0\pmod{x}$ and ${^a _b}F_c\equiv 0\pmod{y}$, so ${^a _b}F_c=x*p_0$ and ${^a _b}F_c=y*q_0$ for some $p_0,q_0\in{\bf Z}$. So, $x\vert{^a _b}F_c$ and $y\vert{^a _b}F_c$, and since $(x,y)=1$, then $xy\vert{^a _b}F_c$ (by Fact 8). So, ${^a _b}F_c\equiv 0\pmod{xy}$. Now, since ${^a _b}F_{c+1}\equiv 1\pmod{x}$ and ${^a _b}F_{c+1}\equiv 1\pmod{y}$, then ${^a _b}F_{c+1}=x*p_1 +1$ and ${^a _b}F_{c+1}=y*q_1 +1$ for some $p_1,q_1\in{\bf Z}$. So, $x\vert({^a _b}F_{c+1}-1)$ and $y\vert({^a _b}F_{c+1}-1)$, and since $(x,y)=1$, then $xy\vert({^a _b}F_{c+1}-1)$ (by Fact 8). So, ${^a _b}F_{c+1}\equiv 1\pmod{xy}$. By Theorem 47, ${^a _b}t(xy)\vert c$, which is what we wanted to show.

Theorem 49   If $\mathbf{(x,y)=1}$, then $\mathbf{{^a _b}t(xy)=[{^a _b}t(x),{^a _b}t(y)]}$.

${^a _b}t(x)\vert[{^a _b}t(x),{^a _b}t(y)]$ and ${^a _b}t(x)\vert[{^a _b}t(x),{^a _b}t(y)]$ (by definition of LCM), and since $(x,y)=1$, then ${^a _b}t(xy)\vert[{^a _b}t(x),{^a _b}t(y)]$ (by Theorem 48). ${^a _b}F_{{^a _b}t(xy)}\equiv 0\pmod{xy}$ and ${^a _b}F_{{^a _b}t(xy)+1}\equiv 1\pmod{xy}$, so ${^a _b}F_{{^a _b}t(xy)}\equiv 0\pmod{x}$ and ${^a _b}F_{{^a _b}t(xy)+1}\equiv 1\pmod{x}$ by Fact 16, so by Theorem 47, ${^a _b}t(x)\vert{^a _b}t(xy)$. Since ${^a _b}F_{{^a _b}t(xy)}\equiv 0\pmod{xy}$ and ${^a _b}F_{{^a _b}t(xy)+1}\equiv 1\pmod{xy}$, so ${^a _b}F_{{^a _b}t(xy)}\equiv 0\pmod{y}$ and ${^a _b}F_{{^a _b}t(xy)+1}\equiv 1\pmod{y}$ by Fact 16, so by Theorem 47, ${^a _b}t(y)\vert{^a _b}t(xy)$. So, by definition of LCM, $[{^a _b}t(x),{^a _b}t(y)]\vert{^a _b}t(xy)$. Since ${^a _b}t(xy)>0$ and $[{^a _b}t(x),{^a _b}t(y)]>0$, by Fact 15 ${^a _b}t(xy)=[{^a _b}t(x),{^a _b}t(y)]$.