\documentstyle[12pt]{article}
% this time, get rid of introductory stuff about Vince
% Also get rid of p^k part, save for future paper
\renewcommand{\baselinestretch}{2}
\newcommand{\zz}{{\bf Z}}
\newcommand{\qed}{$\Box$}
\newcommand{\zm}[1]{\zz_{{#1}}}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\begin{document}
\begin{center}
{\large Periods of generalized Fibonacci sequences modulo $M$}\\
{\bf Kevin Iga}\\
{\footnotesize Pepperdine University, Nat. Sci. Div., 24255 Pacific Coast Hwy.,
Malibu CA 90263}\\
{\footnotesize October, 1999}
\end{center}
In 1960, Wall [4] considered the Fibonacci sequence over the integers
modulo $M$. This sequence is periodic, and Wall, along with [1], [2],
and [3], have asked how to predict this period. The main results are
of this form: if $M=p$ is prime, then the periods must divide
$2(p+1)$, $p-1$, or $p(p-1)$, depending on the congruence class of $p$
modulo 5 [3].
We might hope for a more descriptive formula, say, by replacing the word
``divide'' with ``equal''. As Wall [4] points out, this formula is then
false, with $p=29$, for instance, which has period 14 instead of 28.
As Wall points out, the reason seems analogous to the question of
determining the multiplicative order of 2 modulo $p^k$. We can say
what it must divide, but we don't know what it equals. On the other
hand, it is easy to find what numbers appear as multiplicative orders
modulo $p^k$.
In this paper, we consider an analogously modified question with
Fibonacci sequences modulo $M$. Although we do not predict the period
of the Fibonacci sequence, we generalize the concept of a Fibonacci
sequence modulo $M$, and classify all the periods that may appear.
We will consider sequences (called {\em generalized Fibonacci
sequences}, or {\em GFSs}), with recurrence relation
\[f_{n+2}=a f_n+b f_{n+1}, f_0=c, f_1=d\]
over the integers modulo $M$, where $a$, $b$, $c$, and $d$ are integers
modulo $M$ (the set of integers modulo $M$ we denote $\zm{M}$).
We may say that the sequence $\{f_n\}$ is a GFS of parameters $(a, b, c, d)$.
We will find analogous formulas found by the references mentioned above,
that the period of a GFS must divide particular numbers, but we also show
that all such factors appear as periods of some GFS. Thus we will have
classified all possible periods for a GFS modulo $M$.
The approach follows many of the ideas of Vince [3], in particular, viewing
Fibonacci sequences as sequences in a certain ring extension of $\zm{M}$,
which makes the period equal to the multiplicative order of a certain
element of this ring. The next section is a generalization of Vince's methods.
\section{The ring-theoretic approach}
All our rings will be assumed to be commutative and have a unit.
\begin{proposition}
Let $A$ be a finite ring, and $\{f_n\}$ a GFS in $A$ with
parameters $(a, b, c, d)$. Then the sequence $\{f_n\}$ is periodic for
all $c$ and $d$ if and only if $a$ is invertible in $A$.
\end{proposition}
Proof:
We note that we can reverse the sequence by solving for $f_n$ as long
as $a$ is invertible. Since $A\times A$ is a finite set, it must be
periodic. Conversely, if $a$ is not invertible, then we can choose
two choices for $c$ in which $ac$ gives the same answer. Only one of
these may be periodic.
\qed
As a result, we will primarily be only interested in GFSs where $a$ is
invertible.
Note that there is always a GFS of period 1: \{0, 0, ...\}. In fact,
as long as $a+b-1$ is invertible, it is the only period 1 GFS. This will
be called the {\em trivial GFS}.
Here is the fundamental machine in this method:
\begin{lemma}
Let $A$ be a finite ring, and let $a, b, c, d\in A$, with $a$
invertible in $A$. Let $f_n$ be a GFS in $A$ with parameters $(a, b,
c, d)$. Define the quadratic polynomial
$f(\delta)=\delta^2+b\delta-a$, and let $R$ be the ring
\[R=A[\delta]/(f(\delta)).\]
Then
\[f_n\delta+f_{n+1}=(\delta+b)^n(c\delta+d),\]
and the period of the GFS is the smallest number $T$ so that
\[c\delta+d=(\delta+b)^T(c\delta+d).\]
\label{lem:period}
\end{lemma}
Proof:
As usual, every element of $R$ can be written uniquely as
$x\delta+y$ where $x, y \in A$. Note also that
\[(x\delta+y)(\delta+b)=y\delta+(ax+by).\]
If we consider the sequence $f_n\delta+f_{n+1}$ in $R$, we can see
that this sequence is equivalent to the GFS $f_n$, and satisfies a
first-order relation
\[(f_n\delta+f_{n+1})(\delta+b)=f_{n+1}\delta+(af_n+bf_{n+1})
=f_{n+1}\delta+f_{n+2}.\]
By induction, then we have
\[f_n\delta+f_{n+1}=(\delta+b)^n(c\delta+d).\]
\qed
\begin{lemma}
Let $a, b, c, d\in A$ with $a$ invertible. Define $R$ as above. The
period of a GFS in $A$ with parameters $(a, b, c, d)$ divides the
period of the GFS in $A$ with parameters $(a, b, 0, 1)$, which is
equal to the multiplicative order of $\delta+b$ in $R$, which divides
the maximum multiplicative order in the group $R^\times$.
\end{lemma}
Proof:
The period of the GFS in $A$ with parameters
$(a, b, 0, 1)$ is the smallest number $T_{(0,1)}$ so that
\[(0\delta+1)(\delta+b)^{T_{(0,1)}}=(0\delta+1).\]
Thus, $T_{(0,1)}$ is the multiplicative order of $\delta+b$ in $R$ (note this
also shows $\delta+b$ is invertible). Now,
\[(d\delta+c)(\delta+b)^{T_{(0,1)}}=d\delta+c\]
no matter what $c$ and $d$ are (note the definition of $R$ does not
depend on $c$ or $d$). So the actual period for parameters
$(a, b, c, d)$ divides $T_{(0,1)}$, which is the order of $\delta+b$ in
$R^\times$.
By abelian group theory, the order of any element in the group divides
the maximum order among elements in the group. The lemma follows.
\qed
\section{Modulo primes}
We now take the case $A=\zm{p}$, where $p$ is a prime. Since $A$ is
then a field, we will write $K$ instead of $A$. Actually the
following theorem works when $K$ is an arbitrary finite field with
$p^k$ elements, but this will not be important to us.
\begin{theorem}
Let $K$ be the finite field $K=\zm{p}$, and let $a, b\in K$ with
$a\not=0$. Let $f_n$ be a GFS in $K$, satisfying
\[f_{n+2}=af_n+bf_{n+1}.\]
\begin{enumerate}
\item If $f$ is an irreducible polynomial in $K$, then the period of
$f_n$ divides $p^2-1$.
\item If $f$ has two distinct roots in $K$, then the period of $f_n$
divides $p-1$.
\item If $f$ has a double root in $K$, then the period of $f_n$ divides
$p(p-1)$.
\end{enumerate}
\label{thm:main}
\end{theorem}
Proof:
We consider the ring $R=K[\delta]/(f(\delta))$ as before.
We consider the three cases separately.
Case I:
If $f$ is irreducible in $K$, then $R$ is a field with $p^2$ elements.
Its multiplicative group $R^\times$ is a cyclic group with $p^2-1$ elements.
The maximum order of an element of $R^\times$ is thus $p^2-1$. By the
previous lemma, the period divides $p^2-1$.
Case II:
Now suppose $f$ has two distinct roots $\{r_1, r_2\}$ in $K$. By the Chinese
remainder theorem, there is an isomorphism
\[R^\times\cong K^\times\times K^\times.\]
By the previous corollary, the period is the maximum order of an element in
$K^\times\times K^\times$, which is $p-1$.
Case III:
Now we consider the case when $f$ has a double root, so that
\[f(x)=x^2+bx-a=(x-r)^2.\]
If we let $\epsilon=\delta-r$, we can describe $R$ as
\[R=K[\epsilon](\epsilon^2).\]
Now, $R^\times$ has as subgroups $K^\times\cong \zm{p-1}$ and
$\{x\epsilon+1\}\cong \zm{p}$. These have trivial intersection and
generate the group, so $R^\times\cong \zm{p-1}\times \zm{p}\cong
\zm{p(p-1)}$, which has maximum order is $p(p-1)$.
\qed
\section{All such periods are possible}
As promised in the introduction, we will now see that the periods allowed by
theorem \ref{thm:main} are precisely the periods that may occur.
\begin{theorem}
Let $p$ be a prime. The set of periods of GFSs modulo $p$ of
parameters $(a, b, 0, 1)$ with $a\not=0$ are precisely the integers
greater than 1 dividing $p-1$, $p(p-1)$ and $p^2-1$.
\label{thm:bestbounds}
\end{theorem}
Proof:
Before proving this theorem, it will be convenient to change
variables. Before, from our parameters $(a, b, 0, 1)$, we defined
$R=K[\delta]/f(\delta)$. We now change variables to
$\gamma=\delta+b$. Now $\gamma$ satisfies
\[\gamma^2-b\gamma-a=0\]\
as can be computed directly. Since $\delta\not\in K$, we know
$\gamma\not\in K$, and that this is the defining equation for
$\gamma$. Hence
\[R=K[\gamma]/(\gamma^2-b\gamma-a).\]
The period of the GFS $(a, b, 0, 1)$ is the order of $\gamma$ in
$R^\times$. Furthermore the number of distinct roots of $f$ is the
same as the number of distinct roots of $\gamma^2-b\gamma-a$.
We now consider the three cases mentioned in the proof of Theorem
\ref{thm:main}.
Case I: $T$ divides $p^2-1$ but not $p-1$
Let $T>1$ divide $p^2-1$ but not $p-1$. We will find $a$ and $b$.
We define $R$ to be the unique quadratic field extension of $K$. Now
$R^\times$ is a cyclic group of order $p^2-1$, and since $T$ divides
$p^2-1$, it occurs as an order of some element $\gamma$ in the group.
Since $T$ does not divide $p-1$, we know $\gamma\not\in K^\times$.
Thus, $\gamma$ has a quadratic defining equation. Let $a$ and $b$ be
so that the defining equation is
\[\gamma^2-b\gamma-a=0.\]
Now $a\not=0$ (or the defining equation would be reducible). Thus
the GFS with parameters $(a, b, 0, 1)$ has period $T$.
Case II: $T$ divides $p(p-1)$ but not $p-1$
Let $T>1$ be an integer dividing $p(p-1)$ but not dividing $p-1$. We
define $R=K[\epsilon]/(\epsilon^2)$. As mentioned in the proof of
theorem \ref{thm:main}, $R^\times\cong\zm{p(p-1)}$. Let $\gamma$ be
an element of $R^\times$ of order $T$. Since $T$ does not divide
$p-1$, $\gamma\not\in K^\times$.
Thus, $\gamma$ has a quadratic defining equation as follows:
if $\gamma=x\epsilon+y$, then
\[\gamma^2-2y\gamma+y^2=(\gamma-y)^2=(x\epsilon)^2=0.\]
Then $R=K[\gamma]/(\gamma^2-2y\gamma+y^2)$ and by setting $b=2y$ and $a=-y^2$
we will have that the GFS with parameters
$(-y^2, 2y, 0, 1)$ has period $T$. Note that since $\gamma$ is invertible,
$y\not=0$ so $a\not=0$.
Case III: $T$ divides $p-1$ but is not 1
Let $T>1$ divide $p-1$. We define $R=K\times K$. Since $T$ divides
$p-1$, there is an element $(r_1,r_2)\in K^\times\times K^\times$ with
multiplicative order $T$. In fact, if we insist that $r_2=1$, we can ensure
$r_1\not=r_2$ (here we are using $T\not=1$).
Then we let $b=r_1+r_2$ and $a=-r_1r_2$ (note $a\not=0$). Then
\[\gamma^2-b\gamma-a=(\gamma-r_1)(\gamma-r_2)\]
and
\[g:K[\gamma]/(\gamma^2-b\gamma-a)\to K\times K\]
\[g(x\gamma+y)=(xr_1+y,xr_2+y)\]
is an isomorphism by the Chinese remainder theorem. Under this map,
$g(\gamma)=(r_1,r_2)$, which has multiplicative order $T$. Thus the
GFS with parameters $(a, b, 0, 1)$ has period $T$.
\qed
Note that the trivial GFS covers the factor 1, as long
as we remove the restriction $(c,d)=(0,1)$, so all the factors of
$p^2-1$, $p(p-1)$ and $p-1$ actually appear as periods.
\section{Modulo powers of primes}
We now generalize our previous results to powers of primes. The
following two lemmas are essentially in [1] and [4],
but only for the standard Fibonacci sequence, not for GFSs.
\begin{lemma}
If $f_n$ is a GFS modulo $p^k$ (with $k>1$) with parameters
$(a, b, 0, 1)$, and it has period $T$, then reducing it modulo $p^{k-1}$
results in a GFS of period either $T$ or $T/p$.
\end{lemma}
Proof:
For each $1\le i\le k$ define $R_i=\zm{p^i}[\gamma]/(\gamma^2-b\gamma-a)$ as
usual. Then the multiplicative order of $\gamma$ in $R_k$ is the
period $T$ of the GFS. The ring homomorphism reducing modulo
$p^{k-1}$ restricts to a group epimorphism on the group of units, with
kernel $K'=1+p^{k-1}R_k$. Elements of $K'$ can be written as
$1+p^{k-1}w$, where $w\in R_k$, but $w$ is only determined up to $R_1$, so
there are $p^2$ elements in $K'$.
Now in the binomial expansion of $(1+p^{k-1}w)^p$, all but the first
and last terms have a binomial coefficient with at least one factor of
$p$. All but the first term have some power of $p^{k-1}$; so all the
middle terms have some multiple of $p^k$. If $k>1$, then the last
term has $p^k$ as well. So modulo $p^k$, we have
\[(1+p^{k-1}w)^p=1\]
so that every element in $K'$ (other than 1) has order $p$.
Let $T'$ be the order in $R_{k-1}^\times$. Then $\gamma^{T'}$ must
reduce to 1 modulo $p^{k-1}$ and thus $\gamma^{T'}\in K'$.
Furthermore, only powers of $\gamma^{T'}$ are in $K'$. Since every
element of $K'$ has order $1$ or $p$, it follows that $T$ is either
$T'$ or $pT'$.
\qed
\begin{lemma}
If $f_n$ is a GFS modulo $p^k$ (with $k>2$, but $p^k\not=8$) with
parameters $(a, b, 0, 1)$, and reducing modulo $p^{k-2}$ results in a
GFS of period $T/p$, and reducing modulo $p^{k-1}$ results in a GFS of
period $T$, then $f_n$ has period $pT$.
\end{lemma}
Proof:
Set up $\gamma, R_k$ and so on as before. The hypotheses imply
$\gamma$ is of order $T/p$ in $R_{k-2}$ but of order $T$ in $R_{k-1}$.
This means in $R_{k-1}$,
\[\gamma^{T/p}=1+p^{k-2}w\]
where $w\not\equiv 0\pmod{p}$. Then in $R_k$,
\[\gamma^{T/p}=1+p^{k-2}u\]
for some $u$ that reduces to $w$ in $R_{k-1}$. We now raise both sides to the
$p$th power in $R_k$:
\[\gamma^T=(1+p^{k-2}u)^p=1+p^{k-1}u+\cdots.\]
I claim the higher terms are zero (except for $p=2$ and $k=3$): Since
each binomial coefficient except the first and the last has a factor
of $p$, the $j$-th term has a factor of
\[pp^{j(k-2)}=p^{j(k-2)+1}=p^{(j-1)(k-2)-1+k}\]
so that as long as $(j-1)(k-2)\ge 1$, this is zero modulo $p^k$.
Since $k>2$, this occurs whenever $j>1$. The last term has a factor
of $p^{(p-1)(k-2)-2+k}$, and since $k>2$ and $p\ge 2$ and $p^k\not=8$,
this is zero mod $p^k$.
Thus $\gamma^T=1+p^{k-1}u$, which is not 1. Thus the period of the
GFS is not $T$, and by the previous lemma, is thus $pT$.
\qed
Note: For $p^k=8$, the above lemma is false: consider $f_{n+2}=-f_n$.
This has period 4 in every mod except 2, where it has period 2.
\begin{lemma}
For every GFS with parameters $(a, b, 0, 1)$ modulo $p$, there is a GFS
with parameters $(a', b', 0, 1)$ modulo $p^2$ that reduces to the first
modulo $p$, with period $pT$.
\end{lemma}
Proof:
Let $T$ be the period of the reduction modulo $p$.
Case I: $T$ is not a multiple of $p$.
Take an arbitrary GFS with parameters $(a', b', 0, 1)$ that reduces
modulo $p$ to one with parameters $(a, b, 0, 1)$. This new GFS may
have period $T$, or $pT$. If it has period $pT$ we are done. If it
has period $T$, then construct $R_2$ as before, and note that even if
$\gamma^T=1$, we have
\[(\gamma+p)^T=\gamma^T+Tp\gamma^{T-1}+\cdots=1+Tp\gamma^{-1}\]
where we have used the fact that higher terms in the binomial
expansion all have $p^2$ and higher powers of $p$. Since $T$ is not a
multiple of $p$, we know that $Tp\gamma^{-1}\not=0$, so that the order of
$\gamma+p$ is not $T$.
If we let $\zeta=\gamma+p$, then $\zeta$ satisfies a quadratic relation:
\begin{eqnarray*}
\zeta^2&=&(\gamma+p)^2=\gamma^2+2p\gamma+p^2=b'\gamma+a'+2p\gamma\\
&=&(b'+2p)(\zeta-p)+a'=(b'+2p)\zeta+a'-b'p
\end{eqnarray*}
and we can construct the ring
\[R'=\zm{p^2}[\zeta]/(\zeta^2-(b'+2p)\zeta-a'+b'p).\]
There is a ring homomorphism from $R'$ to $R_2$ taking $\zeta$ to
$\gamma+p$, and this is invertible, since the inverse is a map taking
$\gamma$ to $\zeta-p$. Hence these rings are isomorphic, and the
quadratic relation reduces modulo $p$ to the original equation. This
means that the new GFS with parameters $(a'-b'p, b'+2p, 0, 1)$ has period not
equal to $T$, but since it reduces modulo $p$ to a GFS with period $T$,
it must have period $pT$.
Case II: $T$ is a multiple of $p$.
Note that this may only occur when the quadratic defining polynomial
$f(x)$ for $\gamma$ has a double root modulo $p$. In other words, for
some integer $s$, reducing $f(x)$ modulo $p$ gives $f(x)=(x-s)^2=x^2-2s+s^2$.
We take the GFS $(-s^2,2s,0,1)$ modulo $p^2$, whose period is the order
of $\gamma$ in
\[R_2=\zm{p^2}[\gamma]/((\gamma-s)^2)\]
Let $\epsilon=\gamma-s$. Then $\epsilon^2=0$.
We compute $\gamma^T$:
\[\gamma^T=(s+\epsilon)^T=s^T+Ts\epsilon=s^T-Ts^2+Ts\gamma.\]
Now $s$ is invertible modulo $p^2$ because modulo $p$, $s^2$ is the
constant term of $f(x)$, which is invertible. Also, $T$ has at most
one factor of $p$ because $T$ divides $p(p-1)$. So the $\gamma$
term is non-zero, and $\gamma^T\not=1$. Thus, $\gamma$ is not
order $T$, and thus the GFS does not have period $T$. Since it reduces
to the a GFS of period $T$ when reduced modulo $p$, we know that
it has a period of $pT$.
\qed
\begin{theorem}
Let $p$ be a prime. The set of periods of GFSs modulo $p^k$ of
parameters $(a, b, c, d)$ with $a$ invertible are precisely the integers
dividing $p^{k-1}(p-1)$, $p^k(p-1)$ and $p^{k-1}(p^2-1)$.
\label{thm:bestboundspk}
\end{theorem}
Proof:
Let $T$ be a number dividing one of these. If $T=1$, use the trivial
GFS. Let $T'$ be the result of dividing $T$ by enough factors of $p$
so that $T'$ divides either $p-1$, $p(p-1)$, or $p^2-1$, and so that
$T/T' < p^k$. Write $T/T'$ as $p^n$. Use theorem
\ref{thm:bestbounds} to find a GFS $(a', b', 0, 1)$ modulo $p$ with
period $T'$. In case $p=2$, we may need to start at $p^3=8$, for
which we have a period 8 sequence $(1, 2, 0, 1)$ and a period 12
sequence (the Fibonacci sequence).
Use the previous lemma iteratively to find a GFS $(a'', b'', 0, 1)$
modulo $p^{n+1}$ with period $T$. Multiply each term in the sequence
by $p^{k-n-1}$ to get a GFS $(a, b, 0, p^{k-n-1})$ modulo $p^k$ with
period $T$.
\qed
We cannot in general get GFSs of all periods of the form $(a, b, 0, 1)$.
Even not counting $T=1$, we may need arbitrary starting values if $T$
is a power of $p$. If we take $p^k=5^2=25$, for instance, there is no
period of order 5, since as a quick calculation shows, a GFS with
parameters $(a, b, 0, 1)$ having period 5 requires that $a^2+3ab^2+b^4=0$.
Completing the square, this is equivalent to
\[(a+2^{-1}3b^2)^2=5(2^{-1}b^2)^2.\]
Any perfect square modulo 25 that has a factor of 5 must be zero, so
the equations above demonstrate that 5 divides $b$ and thus $a$, but
this contradicts our requirement that $a$ be invertible.
On the other hand, sometimes powers of $p$ do occur. For instance,
$(-1, -1, 0, 1)$ is a GFS modulo $27$ of period 3.
\section{Other observations}
Now for general $M$, note that by the Chinese remainder theorem,
a GFS mod $p_1^{k_1}\cdots p_m^{k_m}$ can be thought of as an $m$-tuple of
$GFS$s, where the $i$th tuple is the GFS taken mod $p_i^{k_i}$. Hence
the period would be the l.c.m. of the $m$ individual periods.
Note also that this technique allows for calculating how many GFSs
modulo $M$ have each period, and in this way, one can calculate the
``probability'' that the standard Fibonacci sequence is a given
period. The actual formulas are no doubt messy, but for any given
$M$, the calculation would be straightforward. It ignores, however,
the fact that the Fibonacci sequence is special and is hardly a
``random'' GFS.
The calculation would require doing more for the $p^k$ case than we
have done, namely, to calculate the groups
$\left(\zm{p^k}[\gamma]/(f(\gamma))\right)^\times$. This is possible
to do using the above methods directly, although it is somewhat
tedious. The main trick is to reduce mod $p$, calculate the kernel as
above, then figure out the extension by hand. This works for odd $p$,
but for $p=2$, there are many special cases that need to be dealt with
specially.
\section{Acknowledgments}
Many thanks to Bradley Brock for helpful and enjoyable discussions, and to
Curtis Cooper for suggesting references in the literature to this topic.
\section{References}
1. A. Andreassian, Fibonacci Sequences modulo $M$, {\em Fibonacci Quarterly},
1974, pp. 51-64.
\noindent
2. A. Ehrlich, On the Periods of the Fibonacci Sequence Modulo $M$,
{\em Fibonacci Quarterly}, 1989, pp. 11-13.
\noindent
3. A. Vince, The Fibonacci Sequence modulo $N$, {\em Fibonacci Quarterly},
1978, pp. 403-407.
\noindent
4. D. D. Wall, Fibonacci Series Modulo $m$, {\em American Math. Monthly},
1960, pp. 525-532.
AMS Classification Number: 11B39, 11A07, 11B50
\end{document}