\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\def\modd#1 #2{#1\ \mbox{{\rm (mod}} \ #2\mbox{\rm )}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
On Equivalence Classes of \\ 
\vskip .1in
Generalized Fibonacci Sequences
}
\vskip 1cm
\large
Miho Aoki and Yuho Sakai\\
Department of Mathematics\\
Shimane University\\
Matsue, Shimane 690-8504\\
Japan\\
\href{mailto:aoki@riko.shimane-u.ac.jp}{\tt aoki@riko.shimane-u.ac.jp}\\
\href{mailto: s149410@matsu.shimane-u.ac.jp}{\tt s149410@matsu.shimane-u.ac.jp}\\
\end{center}

\vskip .2 in

\hyphenation{non-ze-ro}
\hyphenation{in-vi-si-ble}
\def\noi {\noindent}
\def\Ker {{\rm Ker}}
\def\Im {{\rm Im}}
\def\a {\alpha}
\def\B {\mathcal{B}}
\def\O {\mathcal{O}}
\def\N {\mathbb{N}}
\def\Z {\mathbb{Z}}
\def\Q {\mathbb{Q}}
\def\R {\mathbb{R}}
\def\F {\mathbb{F}}
\def\RR {\mathcal{R}}
\def\QQ {\overline{\Q}}
\def\QQQ {\QQ}
\def\C {\mathbb{C}}
\def\cF {\mathcal{F}}
\def\cR {\mathcal{R}}
\def\e {\epsilon}
\def\d {\mathfrak{d}}
\def\g {\gamma}
\def\fle {\longrightarrow }
\def\k {\kappa}

\begin{abstract}
We consider a {\it generalized Fibonacci sequence} $( G_n )$ by $G_1, G_2 \in \Z$ 
and  $G_n=G_{n-1}+G_{n-2}$ for any integer $n$.  
Let $p$ be a prime number and let $d(p)$ be the smallest positive integer $n$ which satisfies $p \mid F_n$.
In this article, we introduce equivalence relations for the set of generalized Fibonacci sequences.
One of the equivalence relations is defined as follows.
We write $( G_n ) \sim^* (G'_n )$ if there exist integers $m$ and $n$ satisfying
$G_{m+1}G'_n \equiv \modd{G'_{n+1}G_m} {p}$.
We prove the following:  if $p \equiv \modd{\pm 2} {5}$,
then the number of equivalence classes $\overline{ ( G_n )}$  
satisfying $p \nmid G_n$ for any integer $n$ is $(p+1)/d(p)-1$.
If $p \equiv \modd{\pm 1} {5}$, then the number is $(p-1)/d(p)+1$.
Our results are refinements of  a theorem given by K\^{o}zaki and Nakahara in 1999.
They proved that there exists a generalized Fibonacci sequence $( G_n )$
such that $p  \nmid G_n$ for any $n \in \Z$ 
if and only if one of the following three conditions holds:
(1) $p = 5$; (2) $p \equiv \modd{\pm 1} {5}$; (3) $p \equiv \modd{\pm 2} {5}$
and $d(p)<p+1$.
\end{abstract}

\section{Introduction and main results}

We consider a generalized Fibonacci sequence $(G_n )$ defined by 
$$G_1,G_2 \in \Z,\ G_n=G_{n-1}+G_{n-2}\ (n\in \Z).$$
If $G_1 = 1$ and $G_2 = 1$, then it is the Fibonacci sequence $ ( F_n ) $, and if $G_1 = 1$ and $G_2 = 3$, 
then it is the Lucas sequence $ ( L_n ) $. 
It is well-known that such generalized Fibonacci sequences are periodic 
modulo $m$ for any natural numbers $m$.  
For example, the sequence $(F_n  \bmod 3)$ is $\ldots 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, \ldots$ (the period is $8$).  
There are many interesting results concerning the generalized Fibonacci sequences.  
We recommend two books  by Koshy \cite[\S  7]{K} and Nakamura \cite{N} as references.

We fix a prime number $p$, and define two relations $\sim$ and $\sim^*$ for the set of generalized Fibonacci sequences.  
The first relation $\sim$ is defined in our previous paper \cite{AS}.
\begin{definition}\label{relation}   Let $( G_n )$ and $( G_n' )$ be generalized Fibonacci sequences.  
We write $( G_n ) \sim (G_n' )$ if the congruence $G_2G_1' \equiv 
\modd{G_2'G_1} {p}$ holds.
\end{definition}
\begin{definition}\label{relation*}   Let $( G_n )$ and $( G_n' )$ be generalized Fibonacci sequences.  
We write $( G_n ) \sim^* (G_n' )$ if there are some integers $m$ and $n$ satisfying $G_{m+1}G_n'\equiv \modd{G_{n+1}'G_m} {p}$.
\end{definition}

By the definitions, the next lemma follows.
\begin{lemma}
\label{relations}  
If $( G_n ) \sim (G_n' )$, then we have $( G_n ) \sim^* (G_n' )$.
\end{lemma}

Note that if $( G_n )$ satisfies $p \mid G_1$ and $p \mid G_2$, 
then we have $(G_n ) \sim (G_n' )$ and $( G_n ) \sim^* (G_n' )$ for any generalized Fibonacci sequences $( G_n' )$.  
We can  show by the definition  that the first relation $\sim$ is an equivalence relation for the set $\{ ( G_n ) |\ p \nmid G_1$ or $ p \nmid G_2 \}$.  

We will show in \S2 that the second relation $\sim^*$ is also an equivalence relation.  
Since the relations $\sim$ and $\sim^*$ are equivalence relations, we can consider the quotient sets using these relations.  We put
\begin{align*}
X_p &:=\{ (G_n) \ |\ p\nmid G_1 \text{ or } p\nmid G_2 \} /\sim , &
Y_p & := \{ \overline{ (G_n ) } \in X_p \ |\ p\nmid G_n \text{ for any } n \in \Z \}.\\
X_p^*&:=\{ (G_n ) \ |\ p\nmid G_1 \text{ or } p\nmid G_2 \} /\sim^* , &
Y_p^* &:= \{ \overline{ (G_n) } \in X_p^* \ |\ p\nmid G_n \text{ for any } n \in \Z \}.
\end{align*}
The sets $Y_p$ and $Y_p^*$ are well-defined by \cite[Lemma\ 2]{AS} and Lemma \ref{lemma5} in \S2. 
We  considered the set $X_p'= \{ (G_n) \ |\ p\nmid G_1 \text{ and } p\nmid G_2 \} /\sim$ and
$Y_p'= \{ \overline{ (G_n ) } \in X_p' \ |\ p\nmid G_n \text{ for any } n \in \Z \}$ 
instead of $X_p$ and $Y_p$ \cite{AS}. Note that the cardinality of $Y_p$ and $Y_p'$ are equal.
Let $p$ be a prime number and let $d(p)$ be the smallest positive integer $n$ for which $p \mid F_n$.  We proved the following theorem in a previous paper \cite{AS}.

\begin{theorem} [{\cite[Theorem\ 1\ (2)]{AS}}]\label{previous}
$$|Y_p|=p+1-d(p)$$
\end{theorem}

In this article, we will reduce the number of equivalence classes by using the new relation $\sim^*$ instead of $\sim$, and will prove  the following theorem in \S3.

\begin{theorem}\label{main theorem}
\begin{itemize}
\item[$(1)$] If $p\equiv \pm \modd{2} {5}$, then we have $$\displaystyle{ |Y_p^* |=\frac{ |Y_p|}{d(p)} }=\frac{p+1}{d(p)}-1.$$
\item[$(2)$] If $p\equiv \pm \modd{1} {5}$, then we have $$\displaystyle{ |Y_p^*|=2+\frac{|Y_p|-2}{d(p)}}=\frac{p-1}{d(p)}+1.$$
\item[$(3)$] If $p=5$, then we have $|Y_p^*|=|Y_p|=1$.
\end{itemize}
\end{theorem}

In \S4, we will show that our results imply the following result given by K\^{o}zaki and Nakahara in 1999.  
An integer $m$ is called the type of a non-divisor when there exists a generalized Fibonacci sequence $( G_n )$
 such that $m \nmid G_n$ for any $n \in \Z$.  For a prime number $p$, we denote the period of $( F_n  \bmod p)$ by $k(p)$.

\begin{theorem} [{\cite[K\^{o}zaki\ and\ Nakahara]{KN}}]\label{nakahara}   A prime number 
$p$ is the type of non-divisor if and only if one of the following three conditions holds.
\begin{itemize}
\item[$(1)$] $p=5$.
\item[$(2)$] $p \equiv \modd{1, 9, 11, 13, 17, 19} {20}$.
\item[$(3)$] $p \equiv \modd{3, 7} {20}$ and $k(p)<2(p+1)$.
\end{itemize}
\end{theorem}

In \S5, we will give some examples of the cardinalities of the set $Y_p$ and $Y_p^*$. 

\section{Equivalence relations}
In this section, we will give some lemmas on the relation $\sim^*$.  The following lemma follows from the recurrence relation $G_n=G_{n-1}+G_{n-2}$. 

\begin{lemma}
Let $(G_n)$ be a generalized Fibonacci sequence that satisfies $p \nmid G_1$ or $p\nmid G_2$.  
If $p \mid G_n$, then we have $p \nmid G_{n-1}$ and $p \nmid G_{n+1}$.
\label{not-divide}  
\end{lemma}

\begin{lemma}\label{slide}  Let $( G_n)$ and $( G_n' ) $ be generalized Fibonacci sequences.  
If $G_{m+1}G_n' \equiv \modd{G_{n+1}'G_m} {p}$,
then we have $G_{m+2}G_{n+1}'\equiv \modd{G_{n+2}'G_{m+1}} {p}$.
\end{lemma}

\begin{proof}
\begin{align*}
G_{m+2}G_{n+1}' &=(G_{m+1}+G_m)G_{n+1}'  \\
& =G_{m+1}G_{n+1}'+G_m G_{n+1}' \\
& \equiv G_{m+1}G_{n+1}' +G_{m+1}G_n'  \hspace{1cm} \text{(by the assumption)} \\
& =G_{m+1}(G_{n+1}'+G_n' )\\
& =G_{m+1}G_{n+2}'.
\end{align*}
\end{proof}

For any integer $G$ that is not divisible by $p$, we denote an inverse
element modulo $p$ by $G^{-1} \ (\in \Z)$ (i.e., $GG^{-1} \equiv \modd{1} {p}$).
\begin{lemma} \label{equivalence relation}  The relation
$\sim^*$ is an equivalence relation for  the set $\{ (G_n ) \ |\ p
\nmid G_1\ \text{or}\ p \nmid G_2 \}$.
\end{lemma}

\begin{proof} Since this relation  is reflexive and symmetric, we will prove the transitivity: 
if $( G_n ) \sim^* (G_n')$ and $( G_n' ) \sim^* ( G_n'' )$, then $( G_n ) \sim^* ( G_n'' )$.  By the assumption, there exist integers $m, n, k$ and $\ell$ satisfying
\begin{equation} 
G_{m+1}G_n' \equiv \modd{G_{n+1}'G_m} {p} 
\ \ \  \text{and}\ \ \ 
G_{k+1}'G_{\ell}'' \equiv \modd{G_{\ell+1}''G_k'} {p}. \notag
\end{equation}
Put $t= \max (n,k)$.  Using Lemma \ref{slide}, we get integers $m$ and $\ell$ satisfying 
\begin{equation}\label{cong}
G_{m+1}G_t' \equiv \modd{G_{t+1}'G_m} {p}
\ \ \ \text{and} \ \ \ 
G_{t+1}'G_{\ell}'' \equiv \modd{G_{\ell+1}''G_t'} {p}.
\end{equation}

If we assume $p \mid G_t'$, then we get $p\nmid G_{t+1}'$ using Lemma \ref{not-divide}.  From \eqref{cong}, 
we get $p \mid G_m$ and $p \mid G_{\ell}''$.  Therefore we have $( G_n ) \sim^* ( G_n'' )$ 
since $G_{m+1}G_{\ell}'' \equiv 0 \equiv \modd{G_{\ell+1}'' G_m} {p}$.
If we assume $p \mid G_{t+1}'$, 
then we get $( G_n ) \sim^* ( G_n'' )$ by the same argument.  Next, we assume $p\nmid G_t' $ and $p\nmid G_{t+1}'$.
Then we  get $p \nmid G_m$ and $p\nmid G_{\ell}''$ from (\ref{cong}).
Hence we get $G_{m+1}G_m^{-1} \equiv G'_{t+1} {G'_t}^{-1} \equiv 
\modd{G_{\ell+1}'' {G_{\ell}''}^{-1}} {p}$,
and hence $G_{m+1}G_{\ell}'' \equiv \modd{G_{\ell+1}'' G_m} {p}$.
This congruence implies $( G_n ) \sim^* (G_n'' )$. 
\end{proof}

\begin{lemma}\label{lemma5}  Assume $( G_n ) , (G_n' ) \in \{ (G_n ) \ |\ p \nmid G_1 \text{ or } p \nmid G_2 \}$.
If $( G_n ) \sim^* (G_n' )$ and $p\nmid G_n$ for any $n\in \Z$. Then  we have $p\nmid G_n'$ for any $n \in \Z$.
\end{lemma}

\begin{proof} We can assume that there exist integers $m, n$
satisfying $G_{m+1}G_n' \equiv \modd{G_{n+1}'G_m} {p}$.
We assume that there exists an integer $\ell$ such that $p \mid G_{\ell}'$. Due to the periodicity of $ (G_{n}'  \bmod p)$, we can assume $\ell \geq n$.
Using Lemma \ref{slide}, there exists an integer $k$ such that 
$G_{k+1}G_{\ell}'\equiv \modd{G_{\ell+1}'G_{k}} {p}$.
Since $p$ divides $G_{\ell}'$ and does not divide $G_{\ell+1}'$, we get $p \mid G_{k}$.  This contradicts the assumption.
\end{proof}

\begin{lemma}\label{F-is-divides} Let $(G_n)$ be a generalized Fibonacci sequence.  Then there exists an integer $n$ which satisfies $p|G_n$ 
if and only if  $(G_n ) \sim^* (F_n )$.
\end{lemma} 

\begin{proof}  We first assume that there is an integer $n$ that satisfies $p \mid G_n$.  
We have $( G_n )\sim^* (F_n )$ since
$F_{1}G_n \equiv 0\equiv  \modd{G_{n+1}F_0} {p}$ (note that $F_0=0$).

Next, we assume $( G_n ) \sim^* ( F_n )$. Then there must exist some integers $m$ and $n$ satisfying $G_{m+1}F_n \equiv \modd{F_{n+1}G_m} {p}$.
On the other hand, 
since $F_0=0$ and the periodicity of $( F_n  \bmod p)$, there exists an integer $\ell$ satisfying $p |F_{\ell}$ and $\ell \geq n$.
By using Lemma \ref{slide}, we get  an integer $k$ such that $G_{k+1}F_{\ell}\equiv  \modd{F_{\ell+1}G_{k}} {p}$. 
Since $p\nmid F_{\ell+1}$ by Lemma \ref{not-divide}, we have $p \mid G_{k}$. 
\end{proof}

\begin{lemma}
\label{remark lemma}
\leavevmode
\begin{itemize}
\item[$(1)$]  $X_p^*= Y_p^* \cup \{ \overline{ ( F_n ) } \}$.
\item[$(2)$] For any equivalence classes $\overline{( G_n )}$ of $X_p^*$, we can choose the representative $( G_n )$ satisfying $p \nmid G_1, G_2$.
\item[$(3)$] Let  $\overline{( G_n )}$ be an equivalence class of $Y_p^*$.  For any sequences $( G'_n ) \in  \overline{( G_n )}$, we have $p \nmid G'_1, G'_2$.
\end{itemize}
\end{lemma}

\begin{proof} The assertion (1) follows from Lemma \ref{F-is-divides}.  We will prove (2).  If $p \mid G_1$ or $p \mid G_2$, 
then we have $( G_n ) \sim^* ( F_n)$ by Lemma \ref{F-is-divides}.  
Therefore, we have $ \overline{( G_n )}=\overline{( F_n )}$ and $F_1=F_2=1$.  The assertion (3) follows from Lemma \ref{lemma5}. 
\end{proof}

\section{Equivalence classes}
In our previous paper \cite{AS}, we gave the cardinality of the set $Y_p$.  In this section,  using this result, 
we will prove the main theorem (Theorem \ref{main theorem} in \S1) that gives the cardinality of the set $Y_p^*$.
 
\begin{lemma}\label{solutions} Let $p\ (\ne 2,5)$ be a prime number.
\begin{itemize} 
\item[$(1)$] If $p\equiv \modd{\pm 1} {5}$,
then $X^2-X-1=0$ has different two solutions in $\F_p$.
\item[$(2)$] If $p\equiv \modd{\pm 2} {5}$, then $X^2-X-1=0$ does not have a solution in $\F_p$.
\end{itemize}
\end{lemma}

\begin{proof} The solutions of $X^2-X-1=0$ in $\overline{\F}_p$ (the algebraic closure of $\F_p$) are $X=2^{-1} (1\pm \sqrt{5})$.  
By the assumption $p\ne 2,5$, these solutions are different.  We get 
$
2^{-1}(1\pm \sqrt{5}) \in \F_p$ if and only if $\sqrt{5} \in \F_p$. Furthermore, this is equivalent to   
$\displaystyle{ \left( \frac{5}{p} \right) =\left( \frac{p}{5} \right) =1}$, that is, $p \equiv \modd{\pm 1} {5}$.
\end{proof}

We next  define the number $d(p)$ for a prime number $p$, and the sequences $( f_n )$ and $( g_n )$.  These are important in this article.

\begin{definition}\label{integers}  Let $p$ be a prime number.  Let $d(p)$ 
denote the smallest positive integer $n$ which satisfies $F_n \equiv 0$ (mod $p$).

\begin{itemize}
\item[$(1)$] For any integer $n$ which satisfies $n\not\equiv 0$ (mod $d(p)$), we define the integer $f_n \ (0\leq f_n \leq p-1)$ such that $f_n \equiv F_{n+1}F_n^{-1}$ (mod $p$).
\item[$(2)$] Let $( G_n )$ be a generalized Fibonacci sequence that satisfies $p\nmid G_n$ for any $n \in \Z$.
We can then  define the integer $g_n \ (1\leq g_n \leq p-1 )$ such that $g_n\equiv G_{n+1}G_n^{-1}$ (mod $p$).
\end{itemize}

\end{definition}

We will prove some relations between $( f_n )$, $( g_n )$ and $d(p)$.  The following lemma was given in \cite[Lemma\ 3]{AS}.  
 
\begin{lemma}[{\cite[Lemma\ 3]{AS}}] \label{subscript}  Let $m$ and $n$ be 
integers that satisfy $m, n \not\equiv \modd{0} {d(p)}$.
We then have $f_m =f_n$ if and only if $m \equiv \modd{n} {d(p)}$.
\end{lemma}

We can show the following two lemmas by induction on $n$ and the recurrence relation.

\begin{lemma}\label{GF} For any 
$n,m \in \Z$, we have
 $G_n=F_{n-m}G_{m+1}+F_{n-m-1}G_m$.
\end{lemma}

\begin{lemma}\label{-1} For any $n\in \Z$, we have 
$$
G_{n+1}^2-G_nG_{n+1}-G_n^2=-(G_n^2-G_{n-1}G_n-G_{n-1}^2).
$$
\end{lemma}
For  simplicity, we introduce a new  notation. If a generalized Fibonacci sequence $( G_n )$ satisfies
 $G_1=a$ and  $G_2=b$, then we denote it as  $( G_n ) = \left( G(a,b) \right)$.

\begin{theorem}\label{subscript g} Assume that $(G_n )=\left( G(a,b) \right)$ satisfies  $p\nmid G_n$ for any n $\in \Z$.  
Furthermore, let $a$ and $b$ satisfy $b^2-ab-a^2 \not\equiv \modd{0} {p}$.  For any integers $n$ and $m$, we have $g_n = g_m$ if and only if $n \equiv \modd{m} {d(p)}$.
\end{theorem} 

\begin{proof} First, by the definition of $g_n$ and $g_m$, we have $g_n=g_m$ if and only if $G_mG_{n+1}\equiv \modd{G_{m+1}G_n} {p}$.
Since $G_{n+1}=F_{n-m+1}G_{m+1}+F_{n-m}G_m$ and $G_n=F_{n-m}G_{m+1}+F_{n-m-1}G_m$ from Lemma \ref{GF}, 
we have $g_n\equiv g_m$ if and only if 
\begin{equation}\label{g-cong}
G_{m+1}^2F_{n-m}-G_mG_{m+1}(F_{n-m+1}-F_{n-m-1})-G_m^2F_{n-m} \equiv \modd{0} {p}. 
\end{equation}
By Lemma \ref{-1}, for the left side of \eqref{g-cong}, we have
\begin{alignat*}{2} 
G_{m+1}^2F_{n-m}&-G_mG_{m+1}(F_{n-m+1}-F_{n-m-1})-G_m^2F_{n-m} \\
&\equiv G_{m+1}^2F_{n-m}-G_mG_{m+1}F_{n-m}-G_m^2F_{n-m} \\
&\equiv (G_{m+1}^2-G_mG_{m+1}-G_m^2)F_{n-m} \\
& \equiv  (-1)^{m-1} (G_2^2-G_1G_2-G_1^2)F_{n-m} \\
& \equiv \modd{(-1)^{m-1}(b^2-ab-a^2)F_{n-m}} {p}.
\end{alignat*}
By the assumption $b^2-ab-a^2 \not\equiv 0$ (mod $p$), we conclude that $g_n \equiv g_m$ if and only if 
$n\equiv m$ (mod $d(p)$).
\end{proof}

For a generalized Fibonacci sequence $(G_n )$, let $( g_n )$ be the sequence defined in Definition \ref{integers}.

\begin{definition}\label{second period} Assume $( G_n )=\left( G(a,b) \right)$ satisfies $p\nmid G_n$ for any $n\in \Z$.  
We define the {\it second period} of $( G_n )$ by  the period of $( g_n )$.
\end{definition}

Then we get the following corollary concerning the second period.

\begin{corollary}\label{cor of second period} Assume that $( G_n )=\left( G(a,b) \right)$ satisfies $p\nmid G_n$ for any $n\in \Z$.
\begin{itemize}
\item[$(1)$] If $b^2-ab-a^2 \equiv 0$ $($mod $p)$, then the second period of $( G_n )$ is equal to 1.
\item[$(2)$] If $b^2-ab-a^2 \not\equiv 0$ $($mod $p)$, then the second period of $( G_n )$ is equal to $d(p)$.
\end{itemize}
\end{corollary}

\begin{proof} The assertion (2) follows from Theorem \ref{subscript g}.  
We will prove (1) by showing $g_n =g_1 \equiv ba^{-1}$ (mod $p$) for any $n\in \Z$.  
Due to  the periodicity of $ ( G_n )$ mod $p$, it is sufficient to consider $n \in \N$.  
We use the  induction.  When $n=1$, the result is shown.  
We assume that it holds for any natural numbers less than $n+1$.  We then have the following congruences.
\begin{align*}
g_{n+1} & \equiv G_{n+2} G_{n+1}^{-1} \\
& \equiv (G_{n+1}+G_n)(G_n+G_{n-1})^{-1} \\
& \equiv (G_{n+1}G_n^{-1}+1)(1+G_{n-1}G_n^{-1})^{-1} \\
& \equiv (g_n+1)(1+g_{n-1}^{-1} )^{-1} \\
& \equiv (ba^{-1}+1)(1+b^{-1}a)^{-1} \\ 
& \hspace{1cm} \text{ (by the assumption of the second period $1$)} \\ 
& \equiv (ba^{-1}+1)\times \{ b^{-1}a(ba^{-1}+1)\}^{-1} \\
& \equiv ba^{-1} \equiv \modd{g_1} {p}.
\end{align*}
By the above congruences and $1\leq g_1,  g_{n+1} \leq p-1$, we have $g_{n+1} = g_1$.
\end{proof}

\begin{lemma}\label{lem11}  Assume that $(G_n )$ and $(G'_n )$ satisfy $p\nmid G_n, G'_n$ for any $n\in \Z$. 
Let $\nu$ be the second period of $( G'_n )$.  Then we have $( G_n ) \sim^* ( G'_n )$
if and only if there exists an integer $n$ $(1 \le n \le \nu)$ such that $g'_n=g_1 (\equiv G_2G_1^{-1}$ $($mod $p))$. 
\end{lemma}

\begin{proof}
First, we assume $g_n'=g_1$ for an integer $n$ $(1 \le n \le \nu)$.  Then we obtain $G'_{n+1}{G'_n}^{-1} \equiv G_2 G_1^{-1}$ (mod $p$)
and hence we get $( G_n ) \sim^* ( G'_n )$.

Next, we assume $(G_n ) \sim^* ( G'_n )$.  Then there must exist integers $m$ and $n$ such that $G_{m+1}G'_n \equiv G'_{n+1}G_m$ (mod $p$).
By Lemma \ref{slide} on the forward shift index and the periodicity of $ ( G_n )$ mod $p$, there exists an integer $n$ such that $G_2G'_n \equiv G'_{n+1} G_1$ (mod $p$).
Therefore we obtain $g'_n \equiv g_1$ (mod $p$).  We have $g_1=g'_n$ since $1\leq g_1 \leq p-1$ and $1\leq g_n \leq p-1$.
Furthermore, we can choose such an integer $n$ satisfying $1\leq n\leq \nu$ because the period of $( g'_n )$ is equal to $\nu$. 
\end{proof}

Next, we will prove the main theorem in \S1. 

\begin{proof}[Proof of Theorem\ \ref{main theorem}] We can prove  (3) directly using \cite[Corollary\ 1\ (1)]{AS}.  We will prove (1) and (2).  Using \cite[Theorem\ 1\ (1)]{AS}, we obtain
\begin{align*}
Y_p & =X'_p - \{  \overline{ \left(G(1,f_i) \right) }\ |\ 1\leq i\leq d(p)-2 \} \\
X'_p& := \{ (G_n) \ |\ p\nmid G_1 \ \text{and}\ p\nmid G_2 \} /\sim \\
&=\{ \overline{ \left( G(1,b) \right) } \ |\ 1\leq b\leq p-1 \}.\\
\end{align*}
\begin{itemize}
\item[(1)] We consider an equivalence class $\overline{ ( G_n ) } \ \left(\left( G_n ) =( G(1,b) \right) \right)$ of $Y_p$.
Since $p\equiv \modd{\pm 2} {5}$, we have $b^2-b-1 \not\equiv 0$ (mod $p$) because $X^2-X-1=0$ does not have a solution in 
$\F_p$ from  Lemma \ref{solutions} (2).  Therefore, the second period of $( G_n )$ is $d(p)$ from Corollary \ref{cor of second period} (2), 
and all of the values $g_1,g_2 ,\ldots ,g_{d(p)}$ are different from each other from Theorem \ref{subscript g} , where $g_n$ is the integer such that $g_n=G_{n+1}G_n^{-1} $ (mod $p$) and 
$1 \le g_n \le p-1$.  From the definition of the relation $\sim^*$, we have $( G_n ) = ( G(1,b) ) \sim^* ( G(1,g_i ) )$ for any $i \ (1\leq i\leq d(p) )$.  
On the other hand, for any equivalence classes $\overline{ ( G_n' )  } \ \left(( G_n' )=\left( G(1,b') \right) \right)$ of $Y_p$  satisfying $b' \not\equiv  \modd{g_1,\ldots, g_{d(p)}} {p}$,
we have $( G_n ) \nsim^* ( G_n' )$ from Lemma \ref{lem11}.
Then for any class $\overline{\left(G(1,b)\right)}$ in $Y^*_p$, it produces distinct $d(p)$ classes $\overline{\left(G(1,g_i)\right)}\ (1\leq i\leq d(p))$ under the equivalence relation $\sim$.
Therefore we obtain $\displaystyle{ |Y_p^*|=\frac{ |Y_p |}{d(p)} }$.  The last equality: $\displaystyle{\frac{ |Y_p|}{d(p)} }=\frac{p+1}{d(p)}-1$ follows from \cite[Theorem\ 1\ (2)]{AS}.

\item[(2)] If $p \equiv \pm \modd{1} {5}$, then $X^2-X-1=0$ has two different solutions $\alpha$ and $\beta$ in $\F_p$ from Lemma \ref{solutions} (1).
We consider the generalized Fibonacci sequence $\left( G(1,\alpha) \right) =( G_n )$. Since $p\nmid G_n$ for any $n\in \Z$
 from $\alpha^2-\alpha-1 \equiv \modd{0} {p}$,  Lemma \ref{not-divide} and Corollary \ref{cor of second period} (1), we have $\overline{ \left(G(1,\alpha) \right) } \in Y_p$.  
Similarly, we have $\overline{ \left( G(1,\beta) \right) } \in Y_p$. 
Let $b$ be an integer satisfying $1\leq b\leq p-1$.
Since the second periods of $\left( G(1,\alpha)\right)$ and $\left(G(1,\beta) \right)$ are $1$ from Corollary \ref{cor of second period} (1), 
we obtain $\left( G(1,b) \right) \sim^* \left(G(1,\alpha) \right)$ if and only if $b=\alpha$ from Lemma \ref{lem11}.
By these same arguments, we obtain the same result for $\left( G(1,\beta)\right)$.
On the other hand, $d(p)$ classes $\overline{\left(G(1,b)\right)}$ of $Y_p$ satisfying $b\ne \alpha,\beta$ become the same class of $Y_p^*$.  
We obtain $\displaystyle{ |Y_p^*|=2+\frac{ |Y_p|-2}{d(p)} }$, and the last equality follows from \cite[Theorem\ 1\ (2)]{AS}.
\end{itemize} 
\end{proof}

\section{Comparison with a results of K\^{o}zaki and Nakahara}
In the section, we will show that our result implies a result given by K$\hat{\rm o}$zaki and Nakahara in 1999.
 
\begin{definition}\label{non-divisor}  An integer $m$ is called the type of a non-divisor when there exists a generalized Fibonacci sequence $(G_n)$ such that $m \nmid G_n$ for any $n \in \Z$.
\end{definition}

\begin{definition}\label{period} For a prime number $p$, we let $k(p)$ denote the period of $ (F_n  \bmod p)$.
\end{definition}

We can get the following corollary from \cite[Theorem 1 and Corollary 1]{AS}.

\begin{corollary}[{\cite[\ \S1]{AS}}]\label{my cor} A prime number $p$ is the type of non-divisor if and only if one of the following three conditions holds.
\begin{itemize}
\item[$(1)$] $p=5$.
\item[$(2)$] $p\equiv \pm \modd{1} {5}$.
\item[$(3)$] $p\equiv \pm \modd{2} {5}$  and $d(p)<p+1$.
\end{itemize}
\end{corollary} 

We will prove that Theorem \ref{nakahara} in \S1 is equivalent to Corollary \ref{my cor}.  More specifically,  we will prove $(1)$ or $(2)$ or $(3)$ of Theorem \ref{nakahara} 
 holds if and only if $(1)$ or $(2)$ or $(3)$ of Corollary \ref{my cor} holds.

\begin{proof}  First, we prove that if $(1)$ or $(2)$ or $(3)$ of Theorem \ref{nakahara} holds, then one of $(1)$, $(2)$, or  $(3)$ of Corollary \ref{my cor} holds.

The case in which (1) of Theorem \ref{nakahara} holds already.

We assume  that (2) of Theorem \ref{nakahara} holds.  If $p \equiv1, 9, 11, 19$ (mod $20$), then we have $p \equiv \pm 1$ (mod $5$).
If $p \equiv 13, 17$ (mod $20$), then we have $p \equiv \pm 2$ (mod $5$) and $p \equiv 1$ (mod $4$).  Using \cite[Lemma\ 1\ (2)\ and\ Lemma\ 4]{AS}, we have  $d(p)<p+1$.

We assume (3) of Theorem \ref{nakahara} holds.  In this case, we have $p \equiv 3$ (mod $4$) and $p \equiv \pm 2$ (mod $5$).
By $p \equiv \pm 2$ (mod $5$), we have $F_p \equiv -1$ (mod $p$) and $F_{p+1} \equiv 0$ (mod $p$) (cf.~\cite[\S6]{N}), 
and hence we obtain $k(p) \neq p+1$.  If $d(p) = p+1$, then we obtain $p+1 \mid k(p)$ since $d(p) \mid k(p)$.  
However this is a contradiction,
since $k(p) \neq p+1,\ \kappa (p) <2(p+1)$ and $k(p) \mid 2(p+1)$ hold (cf.~\cite[\S9]{N}).  We conclude that $d(p) < p+1$.

Next, we prove that if  $(1)$ or $(2)$ or $(3)$ of Corollary \ref{my cor} holds, then one of $(1)$, $(2)$, or $(3)$ of Theorem \ref{nakahara} holds.  When (1) 
of Corollary \ref{my cor} holds, it is the same as in (1) of Theorem \ref{nakahara}.
  We assume (2) of Corollary \ref{my cor} holds.  If $p \equiv 1$ (mod $5$), then we have $p \equiv 1, 11$ (mod $20$).  
If $p \equiv -1$ (mod $5$), then we have $p \equiv 9, 19$ (mod $20$).

We assume (3) of Corollary \ref{my cor} holds. When $p \equiv 2$ (mod $5$), we have $p \equiv 7, 17$ (mod $20$).  
When $p \equiv -2$ (mod $5$), we have $p \equiv 3, 13$ (mod $20$).  If $p \equiv 13, 17$ (mod $20$), the condition (2) of 
Theorem \ref{nakahara} holds.  We consider the case $p \equiv 3, 7$ (mod $20$). In this case, we have $p \equiv 3$ (mod $4$) and $p \equiv \pm 2$ (mod $5$), 
and hence $k(p) \mid 2(p+1)$.  From the well-known formula $F_{n-1}F_{n+1}-F_n^2 = (-1)^n$, we get $F_{d(p)-1}F_{d(p)+1}-F_{d(p)}^2 \equiv (-1)^{d(p)}$ (mod $p$).  
Therefore we have $F_{d(p)-1}^2 \equiv (-1)^{d(p)}$ (mod $p$) since $F_{d(p)} \equiv 0$ (mod $p$) and $F_{d(p)-1} \equiv F_{d(p)+1}$ (mod $p$).  
If $F_{d(p)-1}^2 \equiv -1$ (mod $p$), then this contradicts  $\left( \displaystyle{\frac{-1}{p}} \right) =-1$ since $p \equiv 3$ (mod $4$).  
If $F_{d(p)-1}^2 \equiv 1$ (mod $p$), then $F_{d(p)-1} \equiv \pm 1$ (mod $p$) holds.  In the case of $F_{d(p)-1} \equiv 1$ (mod $p$), we have $k(p)=d(p)$, 
and hence $k(p)<p+1$.  In the case  of $F_{d(p)-1} \equiv -1$ (mod $p$), we have $k(p) \leq 2d(p)<2(p+1)$ since $F_{2d(p)-1} \equiv 1$ (mod $p$).
\end{proof}
\newpage
\section{Examples}
\begin{table}[!htb]
{\scriptsize
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline $p$ & $d(p)$ & $Y_p$ & $Y_p^*$ \\  \hline \hline 
& & & \\ 
$3$ & $4$ & $\emptyset$ & $\emptyset$ \\ \hline
&  & & \\
$5$ & $5$ & $\overline{ \left( G(1,3) \right) }$ & $\overline{ \left( G(1,3) \right) }$ \\ \hline
& &  &\\
$7$ & $8$ & $\emptyset$ & $\emptyset$ \\ \hline
& & &\\
$11$ & $10$ & $\overline{ \left( G(1,4) \right) },\ \overline{ \left( G(1,8) \right) }$  & $\overline{ \left( G(1,4) \right) },\ \overline{ \left( G(1,8) \right) }$ \\ \hline
&  & &\\
& & $\overline{ \left( G(1,3) \right) },\ \overline{ \left( G(1,4) \right)}, \
\overline{ \left( G(1,5) \right) },\ \overline{ \left( G(1,7) \right) }, $ & \\
$13$ & $7$ & $\overline{ \left( G(1,9) \right) },\ \overline{ \left( G(1,10) \right)}, \
\overline{  \left( G(1,11) \right) }$ & $\overline{ \left(G(1,3) \right)}$ \\ \hline
& & &\\
& & $\overline{ \left( G(1,3) \right) },\ \overline{ \left( G(1,4) \right)}, \
\overline{ \left( G(1,6) \right) },\ \overline{ \left( G(1,7) \right) }, \ \overline{ \left( G(1,9) \right) },$ &\\ 
$17$ & $9$ & $\overline{ \left( G(1,11) \right)}, \ \overline{  \left( G(1,12) \right) }, \
\overline{  \left( G(1,14) \right) },\overline{  \left( G(1,15) \right) }$ & $\overline{  \left( G(1,3) \right) }$\\ \hline
&  & &\\
$19$ & $18$ & $\overline{ \left( G(1,5) \right) }, \overline{ \left( G(1,15) \right) }$  & $\overline{ \left( G(1,5) \right) }, \overline{ \left( G(1,15) \right)}$ \\ \hline
\end{tabular}
\caption{Examples}
\end{center}
}
\end{table}

\section{Acknowledgments} 
We thank the editor and the referee for reading carefully. We also 
express our gratitude to Toru Nakahara for valuable suggestions.

\begin{thebibliography}{99}
\bibitem{AS} M. Aoki and Y. Sakai, On divisibility of generalized Fibonacci numbers, {\it Integers} {\bf 15} (2015), Paper No.\ A31. 
\bibitem{K} T. Koshy, {\it Fibonacci and Lucas Numbers with Applications},
Pure and Applied Mathematics, 2001.
\bibitem{KN} M. K\^{o}zaki and T. Nakahara, On arithmetic properties of generalized Fibonacci sequences, 
{\it Reports of the Faculty of Science and Engineering, Saga University, Mathematics} {\bf 28} (1999), 1--18.
\bibitem{N} S. Nakamura, {\it  Fibonacci S\={u} no Micro Cosmos} (Japanese), Nippon Hyoronsha, 2002.     
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B39.


\noindent \emph{Keywords: }
Fibonacci number, Lucas number, generalized Fibonacci sequence.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 7 2015;
revised versions received January 18 2016; January 20 2016;
January 25 2016.
Published in {\it Journal of Integer Sequences}, February 5 2016.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}