\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}}}

\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}
\newtheorem{problem}[theorem]{Problem}

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

\newtheorem{theoremA}{Theorem}
\renewcommand*{\thetheoremA}{\Alph{theoremA}}

\begin{center}
\vskip 1cm{\LARGE\bf 
Greatest Common Divisors of Shifted \\
\vskip .1in
Fibonacci Sequences Revisited 
}
\vskip 1cm
\large
Annalena Rahn and Martin Kreh\\
Institute of Mathematics and Applied Computer Science \\
University of Hildesheim \\
Samelsonplatz 1 \\
31141 Hildesheim \\
Germany\\
\href{mailto:rahnan@uni-hildesheim.de}{\tt rahnan@uni-hildesheim.de} \\
\href{mailto:kreh@imai.uni-hildesheim.de}{\tt kreh@imai.uni-hildesheim.de} \\
\end{center}

\vskip .2 in

\newcommand{\NN}{\mathbb{N}}
\newcommand{\abs}[1]{\left\vert #1 \right\vert}

\begin{abstract}
In 2011, Chen computed the greatest common divisors of consecutive
shifted Fibonacci numbers $F_n+a$ and $F_{n+1}+a$ for $a \in \lbrace
\pm 1, \pm 2 \rbrace$. He also showed that $\gcd(F_n+a,F_{n+1}+a)$ is
bounded if $a \neq \pm 1$. This was later generalized by Spilker,
who also showed that $\gcd(F_n+a,F_{n+1}+a)$ is periodic if $a \neq \pm
1$. In this article, we compute the greatest common divisor for $a =
\pm 3$ and we show how the results given in this article compare to
bounds derived by Chen and periods derived by Spilker. We further give
a necessary criterion for an integer $d$ to occur as such a greatest
common divisor.
\end{abstract}

\section{Introduction and results}

Let $(F_n)_{n \geq 1}$ be the Fibonacci sequence defined by the recursion
\begin{equation}
F_n = F_{n-1} + F_{n-2}, \quad F_1=F_2=1.
\end{equation}
Using this recursion, $F_n$ can be extended to integer indices, where we have the relation $F_{-n}=(-1)^{n+1} F_n$. In this article, we want to investigate greatest common divisors of the form $\gcd(F_n+a,F_{n+1}+a)$.

It is well known, that $\gcd(F_n+a,F_{n+1}+a)=1$ for all $n$ if $a=0$, i.e., consecutive Fibonacci numbers are coprime. In 1971, Dudley and Tucker \cite{dudtuck} showed that $\gcd(F_n+a,F_{n+1}+a)$ is unbounded for $a = \pm 1$ by showing that
\begin{align}
\gcd(F_{4n+1}+1,F_{4n+2}+1) &= L_{2n}, \\
\gcd(F_{4n+1}-1,F_{4n+2}-1) &= F_{2n}, \\
\gcd(F_{4n+3}-1,F_{4n+4}-1) &= L_{2n+1}.
\end{align}

Here $(L_n)_{n \geq 1}$ denotes the Lucas sequence defined by $L_n=L_{n-1}+L_{n-2}, L_1=1, L_2=3$.

In 2011, Chen \cite{chen} determined $\gcd(F_n+a,F_{n+1}+a)$ for $a \in \lbrace \pm 1, \pm 2 \rbrace$ and proved the following bound. 

\begin{theoremA}[\cite{chen}]
Let $n, a \in \mathbb{Z}$. Then
\begin{itemize}
\item $\gcd(F_{2n-1}+a,F_{2n}+a) \leq \abs{a^2-1}$ if $a \neq \pm 1$.
\item $\gcd(F_{2n}+a,F_{2n+1}+a) \leq a^2+1$.
\end{itemize}
\end{theoremA}

Spilker \cite{spilker} generalized some of Chen's results. Among other, he showed the following theorems (in even greater generality than mentioned here).

\begin{theoremA}[\cite{spilker}]
\label{sp1}
For all $a \in \mathbb{Z}$, $\gcd(F_n+a,F_{n+1}+a)$ divides $a^2+(-1)^n$. If $a \neq \pm 1$, the function $n \mapsto \gcd(F_n+a,F_{n+1}+a)$ is simply periodic and a period $p \leq (a^4-1)^2$ can be chosen by
\begin{equation}
F_p \equiv 0 \pmod {a^4-1}, \quad F_{p+1} \equiv 1 \pmod {a^4-1}.
\end{equation}
\end{theoremA}

\begin{theoremA}[\cite{spilker}]
\label{sp2}
Let $a \in \mathbb{Z}$ with $\abs{a} > 1, k \in \NN$ and $i \in \lbrace 0,1 \rbrace$.
\begin{enumerate}
\item If $F_{2k-i} \equiv \alpha_i \ (\mathrm{mod}\ a^2+1)$ with $0 \leq \alpha_i < a^2+1$, then 
\begin{align}
\gcd(F_{4k}+a,F_{4k+1}+a) &= \gcd(\alpha_0+a \alpha_1,a \alpha_0 - \alpha_1,a^2+1), \\
\gcd(F_{4k-2}+a,F_{4k-1}+a) &= \gcd(\alpha_0+(a-1) \alpha_1,a \alpha_0 - (a+1) \alpha_1,a^2+1).
\end{align}
\item If $F_{2k-i} \equiv \beta_i \ (\mathrm{mod}\ a^2-1)$ with $0 \leq \alpha_i < a^2-1$, then 
\begin{align}
\gcd(F_{4k-1}+a,F_{4k}+a) &= \gcd((a+1)\beta_1,(a-1)\beta_0-a\beta_1,a^2-1), \\
\gcd(F_{4k-3}+a,F_{4k-2}+a) &= \gcd(\beta_0-(a+2)\beta_1,(a-1)\beta_0-(a-1)\beta_1,a^2-1).
\end{align}
\end{enumerate}
\end{theoremA}

Spilker also answered the question in which cases the upper bound of Chen is being attained. To state this, define the \emph{entry point} of $m \in \NN$ as $e(m) := \min \lbrace i \in \NN : m | F_i \rbrace$ (the existence of $e(m)$ follows from \cite[Theorem 1]{wall}).

\begin{theoremA}[\cite{spilker}]
\label{sp3}
Let $\abs{a} >1$. The function $n \mapsto \gcd(F_n+a,F_{n+1}+a)$ has the upper bound $m = a^2+1$ as a value if and only if $e(m)$ is odd and $a \equiv \pm F_{e(m)+1} \ (\mathrm{mod}\ m)$. The function $n \mapsto \gcd(F_n+a,F_{n+1}+a)$ has the value $m = a^2-1$ on the odd integers if and only if $a=2$ or $e(m)$ is even and $a \equiv -F_{e(m)+1} \ (\mathrm{mod}\ m)$.
\end{theoremA}

In this article, we will use Chen's method to determine $\gcd(F_n+a,F_{n+1}+a)$ for $a = \pm 3$. More precisely, we will show the following theorems.

\begin{theorem}
\label{thm1}
We have
\begin{enumerate}
\item $\gcd(F_{4n-1}+3,F_{4n}+3) = \begin{cases} 8, & \text{if } n \equiv 2 \ (\mathrm{mod}\ 3); \\ 1, &\text{otherwise.} \end{cases}$
\item $\gcd(F_{4n}+3,F_{4n+1}+3) = \begin{cases} 2, & \text{if } n \equiv 1 \ (\mathrm{mod}\ 3) \text{ and } n \not\equiv 4 \ (\mathrm{mod}\ 5); \\ 5, & \text{if } n \not\equiv 1 \ (\mathrm{mod}\ 3) \text{ and } n \equiv 4 \ (\mathrm{mod}\ 5); \\ 10, & \text{if } n \equiv 1 \ (\mathrm{mod}\ 3) \text{ and } n \equiv 4 \ (\mathrm{mod}\ 5); \\ 1, &\text{otherwise.} \end{cases}$
\item $\gcd(F_{4n+1}+3,F_{4n+2}+3) = \begin{cases} 4, & \text{if } n \equiv 0 \ (\mathrm{mod}\ 3); \\ 1, &\text{otherwise.} \end{cases}$
\item $\gcd(F_{4n+2}+3,F_{4n+3}+3) = \begin{cases} 2, & \text{if } n \equiv 2 \ (\mathrm{mod}\ 3); \\ 1, &\text{otherwise.} \end{cases}$
\end{enumerate}
\end{theorem}

\begin{theorem}
\label{thm2}
We have
\begin{enumerate}
\item $\gcd(F_{4n-1}-3,F_{4n}-3) = \begin{cases} 2, & \text{if } n \equiv 2 \ (\mathrm{mod}\ 3); \\ 1, &\text{otherwise.} \end{cases}$
\item $\gcd(F_{4n}-3,F_{4n+1}-3) = \begin{cases} 2, & \text{if } n \equiv 1 \ (\mathrm{mod}\ 3); \\ 1, &\text{otherwise.} \end{cases}$
\item $\gcd(F_{4n+1}-3,F_{4n+2}-3) = \begin{cases} 2, & \text{if } n \equiv 0 \ (\mathrm{mod}\ 3); \\ 1, &\text{otherwise.} \end{cases}$
\item $\gcd(F_{4n+2}-3,F_{4n+3}-3) = \begin{cases} 2, & \text{if } n \equiv 2 \ (\mathrm{mod}\ 3) \text{ and } n \not\equiv 1 \ (\mathrm{mod}\ 5); \\ 5, & \text{if } n \not\equiv 2 \ (\mathrm{mod}\ 3) \text{ and } n \equiv 1 \ (\mathrm{mod}\ 5); \\ 10, & \text{if } n \equiv 2 \ (\mathrm{mod}\ 3) \text{ and } n \equiv 1 \ (\mathrm{mod}\ 5); \\ 1, &\text{otherwise.} \end{cases}$
\end{enumerate}
\end{theorem}

We will further examine the sets
\begin{equation}
G_0(a) := \lbrace \gcd(F_{2n}+a,F_{2n+1}+a): n \in \mathbb{Z} \rbrace \text{ and } G_1(a) := \lbrace \gcd(F_{2n+1}+a,F_{2n+2}+a): n \in \mathbb{Z} \rbrace.
\end{equation}
Let $D(n)$ denote the set of divisors of $n$.
We already know from Theorem \ref{sp1}
that $G_0(a) \subset D(a^2+1)$ and $G_1(a) \subset D(a^2-1)$ 
Theorem \ref{sp3} characterizes the cases in which $a^2+1 \in G_0(a)$ and $a^2-1 \in G_1(a)$. We will show the following extension.

\begin{theorem} \leavevmode
\label{thm3}
\begin{enumerate}
\item We have $1 \in G_0(a)$ and $\lbrace 1,a+1 \rbrace \subset G_1(a)$ for all $a$.
\item We have $2 \in G_0(a)$ if and only if $a \equiv 1 \ (\mathrm{mod}\ 2)$ and $2 \in G_1(a)$ if and only if $a \equiv 1 \ (\mathrm{mod}\ 4)$.
\item Let $d \neq 1,2$ be a divisor of $a^2+1$. If $d \in G_0(a)$, then $e(d)$ is odd and $a \equiv \pm F_{e(d)+1} \ (\mathrm{mod}\ d)$.
\item Let $d \neq 1,2$ be a divisor of $a^2-1$ such that $a \not\equiv \pm 1 
\ (\mathrm{mod}\ d)$. If $d \in G_1(a)$, then $e(d)$ is even and $a \equiv -F_{e(d)+1} \ (\mathrm{mod}\ d)$.
\end{enumerate}
\end{theorem}

Before proving Theorems \ref{thm1}, \ref{thm2}, and \ref{thm3}, we will start with some lemmas in the next section. In Section \ref{secweiter}, we will compare our results to those of Spilker and raise some new questions.

\section{Preliminaries}

We will need a few results about divisibility and greatest common divisors of Fibonacci numbers. We will state common facts without proof and prove some special identities. In the following we always assume that $n$ is a (not necessarily positive) integer.

\begin{lemma}
\label{lemggt}
For all $a,b,c \in \mathbb{Z}$ we have $\gcd(a,bc) = \gcd(a,\gcd(a,b)c)$.
\end{lemma}

\begin{lemma}[\cite{koshy}]
\label{divrules}
We have the following identities and rules about divisibility and greatest common divisors of Fibonacci numbers.
\begin{itemize}
\item For all $m,n \in \NN$ we have $F_{m+n} = F_{m+1}F_n + F_{m}F_{n-1}$.
\item For all $n \in \NN$ we have $F_{n+1}F_{n-1} = F^2_{n} + (-1)^{n}$.
\item $F_n \equiv 0 \ (\mathrm{mod}\ 2) \Leftrightarrow n \equiv 0 \ (\mathrm{mod}\ 3)$.
\item $F_n \equiv 0 \ (\mathrm{mod}\ 4) \Leftrightarrow n \equiv 0 \ (\mathrm{mod}\ 6)$.
\item $F_n \equiv 0 \ (\mathrm{mod}\ 5) \Leftrightarrow n \equiv 0 \ (\mathrm{mod}\ 5)$.
\item $F_n \equiv 0 \ (\mathrm{mod}\ 8) \Leftrightarrow n \equiv 0 \ (\mathrm{mod}\ 6)$.
\item For all $n \in \NN$ we have $\gcd(F_{n},F_{n+1})=1$.
\item For all $m,n \in \NN$ we have $\gcd(F_m,F_n) = F_{\gcd(m,n)}$.
\end{itemize}
\end{lemma}

\begin{lemma}
\label{lem2}
For all $n \in \mathbb{Z}$ we have
\begin{equation}
\gcd(F_{2n},4) = \begin{cases} 4, & \text{if } n \equiv 0 \pmod 3; \\ 1, &\text{otherwise.} \end{cases}
\end{equation}
\end{lemma}
\begin{proof}
Let $n=3m+k$ with $k \in \lbrace -1,0,1 \rbrace$. 
Then we get with Lemma \ref{divrules} 
\begin{equation}
\gcd(F_{2n},4) = \gcd(F_{6m+2k},4) = \begin{cases} 4, & \text{if } k=0; \\ 1, &\text{otherwise.} \end{cases}
\end{equation}
\end{proof}

\begin{lemma}
\label{lem4}
For all $n \in \mathbb{Z}$ we have
\begin{equation}
\gcd(10,F_{2n-1}-2F_{2n}) = \begin{cases} 2, & \text{if } n \equiv 2 \pmod 3; \\ 1, &\text{otherwise.} \end{cases}
\end{equation}
\end{lemma}
\begin{proof}
Analogously to above, $F_{2n-1}-2F_{2n}$ is divisible by $2$ if and only if $2n-1 \equiv 0 \ (\mathrm{mod}\ 3)$, i.e., if $n \equiv 2 \ (\mathrm{mod}\ 3)$. Further we have
\begin{equation}
F_{2n-1}-2F_{2n} = -(3F_{2n-2}+F_{2n-3}) = -(4F_{2n-3}+3F_{2n-4})
\end{equation}
and for any residue class of $n$ modulo $5$ we can pick one of the three terms above such that one summand is divisible by $5$ while the other is not (for example, if $n \equiv 4 \ (\mathrm{mod}\ 5)$ then $F_{2n-3}$ is divisible by $5$ and $3F_{2n-2}$ is not divisible by $5$ due to Lemma \ref{divrules}). Thus $F_{2n-1}-2F_{2n}$ is not divisible by $5$.
\end{proof}

\begin{lemma}
\label{lem3}
For all $n \in \mathbb{Z}$ we have
\begin{equation}
\gcd(10,F_{2n-1}-3F_{2n}) = \begin{cases} 2, & \text{if } n \equiv 1 \pmod 3 \text{ and } n \not\equiv 4 \pmod 5; \\ 5, & \text{if } n \not\equiv 1 \pmod 3 \text{ and } n \equiv 4 \pmod 5; \\ 10, & \text{if } n \equiv 1 \pmod 3 \text{ and } n \equiv 4 \pmod 5; \\ 1, &\text{otherwise.} \end{cases}
\end{equation}
\end{lemma}
\begin{proof}
It suffices to show that $2|F_{2n-1}-3F_{2n}$ if and only if $n \equiv 1 \ (\mathrm{mod}\ 3)$ and $5|F_{2n-1}-3F_{2n}$ if and only if $n \equiv 4 \ (\mathrm{mod}\ 5)$. With Lemma \ref{divrules}, $F_{2n-1}-3F_{2n} = -F_{2n-2}-2F_{2n}$ is divisible by $2$ if and only if $2n-2 \equiv 0 \ (\mathrm{mod}\ 3)$, i.e., if $n \equiv 1 \ (\mathrm{mod}\ 3)$ and $F_{2n-1}-3F_{2n} = -5F_{2n}+F_{2n+2}$ is divisible by $5$ if and only if $2n+2 \equiv 0 \ (\mathrm{mod}\ 5)$, i.e., if $n \equiv 4 \ (\mathrm{mod}\ 5)$.
\end{proof}

\begin{lemma}
\label{lem5}
For all $n \in \mathbb{Z}$ we have
\begin{equation}
\gcd(8,4F_{2n} - F_{2n-1}) = \begin{cases} 2, & \text{if } n \equiv 2 \pmod 3; \\ 1, &\text{otherwise.} \end{cases}
\end{equation}
\end{lemma}
\begin{proof}
Let $n=3m+k$ with $k \in \lbrace -1,0,1 \rbrace$. 
Then we get with Lemma \ref{divrules} 
\begin{equation}
F_{2n-1} = F_{6m+2k-1} \equiv \begin{cases} 2 \pmod 4, & \text{if } k=-1; \\ 1 \pmod 2, &\text{otherwise,} \end{cases}
\end{equation}
and this shows the lemma.
\end{proof}

\begin{lemma}
\label{lem6}
For all $n \in \mathbb{Z}$ we have
\begin{equation}
\gcd(10,F_{2n-1}+3F_{2n}) = \begin{cases} 2, & \text{if } n \equiv 1 \pmod 3; \\ 1, &\text{otherwise.} \end{cases}
\end{equation}
\end{lemma}
\begin{proof}
Since $F_{2n-1} + 3F_{2n} = F_{-2n+1} - 3F_{-2n} = F_{-2n-1} - 2F_{-2n}$, this follows from Lemma \ref{lem4}.
\end{proof}

\begin{lemma}
\label{lem7}
For all $n \in \mathbb{Z}$ we have
\begin{equation}
\gcd(10,F_{2n+1}+3F_{2n}) = \begin{cases} 2, & \text{if } n \equiv 2 \pmod 3 \text{ and } n \not\equiv 1 \pmod 5; \\ 5, & \text{if } n \not\equiv 2 \pmod 3 \text{ and } n \equiv 1 \pmod 5; \\ 10, & \text{if } n \equiv 2 \pmod 3 \text{ and } n \equiv 1 \pmod 5; \\ 1, &\text{otherwise.} \end{cases}
\end{equation}
\end{lemma}
\begin{proof}
Since $F_{2n+1}+3F_{2n} = F_{-2n-1} - 3F_{-2n}$, this follows from Lemma \ref{lem3}.
\end{proof}

The following lemma due to Chen is the main part for computing the greatest common divisors.

\begin{lemma}[\cite{chen}]
\label{chen}
For all $m,k,a \in \mathbb{Z}$ we have
\begin{equation}
\gcd(F_m + a, F_{m+1} + a) = \gcd(F_{m-2k}+aF_{2k-1},F_{m-(2k+1)}-aF_{2k}).
\end{equation}
\end{lemma}

\section{Proof of Theorem \ref{thm1} and Theorem \ref{thm2}}

In this section we will give the proof for Theorems \ref{thm1} and \ref{thm2}.

\begin{proof}[Proof of Theorem \ref{thm1}] \leavevmode
\begin{enumerate}
\item We use Lemma \ref{chen} with $m=4n-1,k=n,a=3$ to get
\begin{align}
\gcd(F_{4n-1}+3,F_{4n}+3) &= \gcd(4F_{2n-1},F_{2n-2}-3F_{2n}) = \gcd(4F_{2n-1},F_{2n+2}) \\
&= \gcd(4F_{2n-1}+4F_{2n+2},F_{2n+2}) = \gcd(8F_{2n+1},F_{2n+2}).
\end{align}
Since $\gcd(F_{2n+1},F_{2n+2})=1$, we get with Lemma \ref{divrules}
\begin{equation}
\gcd(F_{4n-1}+3,F_{4n}+3) = \gcd(8,F_{2n+2}) = \gcd(F_6,F_{2n+2}) = F_{\gcd(6,2n+2)},
\end{equation}
and since
\begin{equation}
\gcd(6,2n+2) = \begin{cases} 6, & \text{if } n \equiv 2 \pmod 3; \\ 2, &\text{otherwise,} \end{cases}
\end{equation}
this proves the first case.
\item We use Lemma \ref{chen} with $m=4n,k=n,a=3$ to get
\begin{align}
\gcd(F_{4n}+3,F_{4n+1}+3) &= \gcd(F_{2n}+3F_{2n-1},F_{2n-1}-3F_{2n}) \\
&= \gcd(F_{2n}+3F_{2n-1}-3(F_{2n-1}-3F_{2n}),F_{2n-1}-3F_{2n}) \\
&= \gcd(10F_{2n},F_{2n-1}-3F_{2n}).
\end{align}
With Lemma \ref{lemggt} we get
\begin{align}
\gcd(F_{4n}+3,F_{4n+1}+3) &= \gcd(10 \cdot \gcd(F_{2n},F_{2n-1}-3F_{2n}),F_{2n-1}-3F_{2n}) \\
&= \gcd(10,F_{2n-1}-3F_{2n}),
\end{align}
thus the claim follows with Lemma \ref{lem3}.
\item We use Lemma \ref{chen} with $m=4n+1,k=n,a=3$ and Lemma \ref{lemggt} to get
\begin{align}
\gcd(F_{4n+1}+3,F_{4n+2}+3) &= \gcd(F_{2n+1}+3F_{2n-1},2F_{2n}) \\
&= \gcd(F_{2n}+4F_{2n-1},2 \cdot \gcd(F_{2n}+4F_{2n-1},F_{2n})) \\
&= \gcd(F_{2n}+4F_{2n-1},2 \cdot \gcd(4,F_{2n})).
\end{align}
With Lemma \ref{lem2} and Lemma \ref{divrules} we get
\begin{align}
&\gcd(F_{2n}+4F_{2n-1},2 \cdot \gcd(4,F_{2n})) \\
&= \begin{cases} \gcd(F_{2n}+4F_{2n-1},8) = \gcd(4F_{2n-1},8) = 4, & \text{if } n \equiv 0 \pmod 3; \\
\gcd(F_{2n}+4F_{2n-1},2) = \gcd(F_{2n},2) = 1, &\text{otherwise.} \end{cases}
\end{align}
\item We use Lemma \ref{chen} with $m=4n+2,k=n,a=3$ to get
\begin{align}
\gcd(F_{4n+2}+3,F_{4n+3}+3) &= \gcd(F_{2n+2}+3F_{2n-1},F_{2n+1}-3F_{2n}) \\
&= \gcd(2F_{2n}+4F_{2n-1},F_{2n-1}-2F_{2n}) \\
&= \gcd(10F_{2n},F_{2n-1}-2F_{2n}).
\end{align}
With Lemma \ref{lemggt} we get
\begin{align}
\gcd(F_{4n+2}+3,F_{4n+3}+3) &= \gcd(10 \cdot \gcd(F_{2n},F_{2n-1}-2F_{2n}),F_{2n-1}-2F_{2n}) \\
&= \gcd(10,F_{2n-1}-2F_{2n}),
\end{align}
hence the statement follows with Lemma \ref{lem4}.
\end{enumerate}
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm2}] \leavevmode
\begin{enumerate}
\item We use Lemma \ref{chen} with $m=4n-1,k=n,a=-3$ to get
\begin{align}
\gcd(F_{4n-1}-3,F_{4n}-3) &= \gcd(2F_{2n-1},F_{2n-2}+3F_{2n}) \\
&= \gcd(2F_{2n-1},4F_{2n}-F_{2n-1}) \\
&= \gcd(8F_{2n},4F_{2n}-F_{2n-1}).
\end{align}
Using Lemma \ref{lemggt} we get
\begin{align}
\gcd(F_{4n-1}-3,F_{4n}-3) &= \gcd(8 \cdot \gcd(F_{2n},4F_{2n}-F_{2n-1}),4F_{2n}-F_{2n-1}) \\
&= \gcd(8,4F_{2n}-F_{2n-1}),
\end{align}
thus the claim folows with Lemma \ref{lem5}.
\item We use Lemma \ref{chen} with $m=4n,k=n,a=-3$ to get
\begin{equation}
\gcd(F_{4n}-3,F_{4n+1}-3) = \gcd(F_{2n}-3F_{2n-1},F_{2n-1}+3F_{2n}) = \gcd(10F_{2n},F_{2n-1}+3F_{2n}).
\end{equation}
Using Lemma \ref{lemggt} gives
\begin{align}
\gcd(F_{4n}-3,F_{4n+1}-3) &= \gcd(10 \cdot \gcd(F_{2n},F_{2n-1}+3F_{2n}),F_{2n-1}+3F_{2n}) \\
&= \gcd(10,F_{2n-1}+3F_{2n}),
\end{align}
and Lemma \ref{lem6} gives the result.
\item We use Lemma \ref{chen} with $m=4n+1,k=n,a=-3$ to get
\begin{align}
\gcd(F_{4n+1}-3,F_{4n+2}-3) &= \gcd(F_{2n+1}-3F_{2n-1},4F_{2n}) \\
&= \gcd(F_{2n-3},8F_{2n-1}-4F_{2n-3}) = \gcd(F_{2n-3},8F_{2n-1}) \\
&= \gcd(F_{2n-3},8) = \gcd(F_{2n-3},F_6).
\end{align}
Using Lemma \ref{divrules} gives $\gcd(F_{4n+1}-3,F_{4n+2}-3) = F_{\gcd(6,2n-3)}$, and since
\begin{equation}
\gcd(6,2n-3) = \begin{cases} 3, & \text{if } n \equiv 0 \pmod 3; \\ 1, &\text{otherwise,} \end{cases}
\end{equation}
we get
\begin{equation}
\gcd(F_{4n+1}-3,F_{4n+2}-3) = F_{\gcd(2n-3,6)} = \begin{cases} F_3 = 2, & \text{if } n \equiv 0 \pmod 3; \\ F_1 = 1, &\text{otherwise.} \end{cases}
\end{equation}
\item We use Lemma \ref{chen} with $m=4n+2,k=n,a=-3$ to get
\begin{align}
\gcd(F_{4n+2}-3,F_{4n+3}-3) &= \gcd(F_{2n+2}-3F_{2n-1},F_{2n+1}+3F_{2n}) \\
&= \gcd(4F_{2n}-2F_{2n+1},F_{2n+1}+3F_{2n}) \\
&= \gcd(10F_{2n},F_{2n+1}+3F_{2n}).
\end{align}
Using Lemma \ref{lemggt}, we get $\gcd(F_{4n+2}-3,F_{4n+3}-3) = \gcd(10,F_{2n+1}+3F_{2n})$, hence the statement follows with Lemma \ref{lem7}.
\end{enumerate}
\end{proof}

\section{Proof of Theorem \ref{thm3}}

To prove Theorem \ref{thm3}, we first note that 
\begin{align}
\gcd(F_0+a,F_1+a) &= \gcd(a,a+1) = 1, \\
\gcd(F_1+a,F_2+a) &= \gcd(a+1,a+1) = a+1, \\
\gcd(F_3+a,F_4+a) &= \gcd(a+2,a+3) = 1.
\end{align}
This proves the first statement. For the second statement, note that $a$ has to be odd, since otherwise $2 \nmid a^2 \pm 1$. So suppose that $a$ is odd. Then we have
\begin{equation}
\gcd(F_4+a,F_5+a) = \gcd(a+3,a+5) = 2,
\end{equation}
hence $2 \in G_0(a)$. We turn our attention to $G_1(a)$. First let $a \equiv 1 \ (\mathrm{mod}\ 4)$. We have $\gcd(F_7+a,F_8+a) = \gcd(F_7+a,F_6) | 8$ and $F_7+a \equiv 2 \ (\mathrm{mod}\ 4), F_8+a \equiv 2 \ (\mathrm{mod}\ 4)$, hence
\begin{equation}
2 = \gcd(F_7+a,F_8+a) \in G_1(a).
\end{equation}

Assume now that $a \equiv 3 \ (\mathrm{mod}\ 4)$. We will use the formula of the greatest common divisor given in Theorem \ref{sp2}. Let
\begin{equation}
A_1 := (a+1) \beta_1, \quad B_1 := (a-1)\beta_0 - a \beta_1, \quad A_2 := \beta_0 - (a+2) \beta_1, \quad B_2 := (a-1) \beta_0 - (a-1) \beta_1,
\end{equation}
where $\beta_0, \beta_1$ are defined as in Theorem \ref{sp2}. Since $a^2-1 \equiv 0 \ (\mathrm{mod}\ 4)$, we can only have $2 \in G_1(a)$ if there is an $i \in \lbrace 1,2 \rbrace$ such that both $A_i$ and $B_i$ are even and further $A_i \equiv 2 \ (\mathrm{mod}\ 4)$ or $B_i \equiv 2 \ (\mathrm{mod}\ 4)$. 

\begin{itemize}
\item Then we have $A_1 \equiv 0 \ (\mathrm{mod}\ 4)$ in any case.
\item We have $B_1 \equiv 2 \ (\mathrm{mod}\ 4)$ if and only if $2 \beta_0+\beta_1 \equiv 2 \ (\mathrm{mod}\ 4)$. Since $\beta_i \equiv F_{2k-i} \ (\mathrm{mod}\ a^2-1)$, this holds if and only if $2F_{2k}+F_{2k-1} \equiv 2 \ (\mathrm{mod}\ 4)$, i.e., if and only if $F_{2k+2} \equiv 2 \ (\mathrm{mod}\ 4)$. From Lemma \ref{divrules}, this holds if and only if $2k+2 \equiv 0 \ (\mathrm{mod}\ 3)$ and $2k+2 \not\equiv 0 \ (\mathrm{mod}\ 6)$, which is impossible.
\item We have $A_2 \equiv  2 \ (\mathrm{mod}\ 4)$ if and only if $\beta_0-\beta_1 \equiv 2 \ (\mathrm{mod}\ 4)$. This is the case precisely when $F_{2k}-F_{2k-1} = F_{2k-2} \equiv 2 \ (\mathrm{mod}\ 4)$. From Lemma \ref{divrules}, this holds if and only if $2k-2 \equiv 0 \ (\mathrm{mod}\ 3)$ and $2k-2 \not\equiv 0 \ (\mathrm{mod}\ 6)$, which is impossible. 
\item Finally, we have $B_2 \equiv 2 \ (\mathrm{mod}\ 4)$ if and only if $\beta_0-\beta_1 \equiv 1 \ (\mathrm{mod}\ 2)$, in which case we also have $A_2 \equiv 1 \ (\mathrm{mod}\ 2)$.
\end{itemize}

Hence $2 \notin G_1(a)$ if $a \equiv 3 \ (\mathrm{mod}\ 4)$.

For the proof of the fourth statement, we mimic Spilker's proof of Theorem \ref{sp3}. We use the identity $F_{m+n} = F_{m+1}F_n + F_{m}F_{n-1}$ from Lemma \ref{divrules} to find, that the integers $F_1,F_2,\ldots$ are modulo $d$ equivalent to
\begin{align}
&F_1,& &F_2,& &\ldots,& &F_{e(d)-1},& &0,& \\
&F_{e(d)+1} F_1,& &F_{e(d)+1} F_2,& &\ldots,& &F_{e(d)+1} F_{e(d)-1},& &0,& \\
&F^2_{e(d)+1} F_1,& &F^2_{e(d)+1} F_2,& &\ldots,& &F^2_{e(d)+1} F_{e(d)-1},& &0,& \ldots
\end{align}
where $F_n^k := (F_n)^k$. Hence
\begin{equation}
\label{eqsp1}
F_{ke(d)} \equiv 0 \pmod d \text{ and } F_{ke(d)+1} \equiv F^k_{e(d)+1} \pmod d \text{ for all } k \in \mathbb{N}.
\end{equation}
From Lemma \ref{divrules}, we get
\begin{align}
F_{e(d)+1} &= F_{e(d)} + F_{e(d)-1} \equiv F_{e(d)-1} \pmod d, \\
F_{e(d)+1}F_{e(d)-1} &= F^2_{e(d)} + (-1)^{e(d)} \equiv (-1)^{e(d)} \pmod d,
\end{align}
hence we further have
\begin{equation}
\label{eqsp2}
F^2_{e(d)+1} \equiv (-1)^{e(d)} \pmod d.
\end{equation}
We begin with the set $G_0(a)$. Suppose that $d \in G_0(a)$, i.e.,
\begin{equation}
d = \gcd(F_{n_0}+a,F_{n_0+1}+a) = \gcd(F_{n_0}+a,F_{n_0-1})
\end{equation}
for some even integer $n_0$. Then $F_{n_0}+a \equiv 0 \ (\mathrm{mod}\ d)$ and $F_{n_0-1} \equiv 0 \ (\mathrm{mod}\ d)$. From \cite[Theorem 3]{wall}, $n_0-1$ is a multiple of $e(d)$, i.e., $n_0 = ke(d)+1$ for some $k \in \mathbb{Z}$. Since $n_0$ is even, $k$ and $e(d)$ are odd, thus \eqref{eqsp1} and \eqref{eqsp2} give
\begin{equation}
F_{n_0} = F_{ke(d)+1} \equiv F^k_{e(d)+1} \equiv (-1)^{\frac{k-1}{2}} F_{e(d)+1} \pmod d,
\end{equation}
hence $a \equiv \pm F_{e(d)+1} \ (\mathrm{mod}\ d)$, and this proves the statement for $G_0(a)$.

The statement for the set $G_1(a)$ can be proved almost analogously. Since here $n_0$ is odd, $ke(d)$ is even. If $k$ was even, we would get
\begin{equation}
F_{n_0} \equiv F^k_{e(d)+1} \equiv \pm 1 \pmod d,
\end{equation}
hence $a \equiv \pm 1 \ (\mathrm{mod}\ d)$. This contradiction yields that $k$ is odd, thus $e(d)$ is even and we get 
\begin{equation}
a \equiv -F_{n_0} \equiv -F_{e(d)+1}^k \equiv -\left((-1)^{e(d)}\right)^{\frac{k-1}{2}} F_{e(d)+1} \equiv -F_{e(d)+1} \pmod d.
\end{equation}

\section{Remarks and future work}
\label{secweiter}

In this section we will briefly compare our results to the general results of Spilker \cite{spilker}. 

For $a = \pm 2$, Theorems \ref{sp1}, \ref{sp2}, and \ref{sp3} state, that $\gcd(F_n \pm 2,F_{n+1} \pm 2)$ is a divisor of $5$ respectively $3$, a period of $\gcd(F_n \pm 2,F_{n+1} \pm 2)$ is given by $40$, and since
\begin{equation}
e(3)=4, \quad F_5=5 \equiv 2 \pmod 3 \qquad \text{ and } \qquad e(5)=5, \quad F_6=8\equiv -2 \pmod 5,
\end{equation}
the values $3$ and $5$ are attained. The exact values of $\gcd(F_n \pm 2,F_{n+1} \pm 2)$ can be found in \cite{chen} and \cite{spilker}, it turns out, that $40$ is indeed the smallest period.

For $a = \pm 3$, Theorems \ref{sp1}, \ref{sp2}, and \ref{sp3} state, that $\gcd(F_n \pm 3,F_{n+1} \pm 3)$ is a divisor of $10$ respectively $8$, a period of $\gcd(F_n \pm 3,F_{n+1} \pm 3)$ is given by $120$, and since
\begin{equation}
e(8)=6, \quad F_7=13 \equiv -3 \pmod 8 \qquad \text{ and } \qquad e(10)=15, \quad F_{16} = 987 \equiv -3 \pmod {10},
\end{equation}
the values $8$ and $10$ are attained. Theorem \ref{thm3} additionally states, that the value $2$ is attained by $\gcd(F_{n_0} \pm 3,F_{n_0+1} \pm 3)$ for some even $n_0$, while it is attained for some odd $n_0$ only in the case $a=-3$. This, together with Theorems \ref{thm1} and \ref{thm2}, shows that the cases $a = \pm 3$ are the first ones, in which not every divisor of $a^2+1$ respectively $a^2-1$ occurs as a greatest common divisor. From the exact values computed in Theorems \ref{thm1} and \ref{thm2}, we also see that the smallest period of $\gcd(F_n \pm 3,F_{n+1} \pm 3)$ is not $120$, but $60$.

These observations give rise to some new questions:

\begin{problem}
Given $a \in \mathbb{Z}$ with $\abs{a} \geq 2$, what is the smallest period of $\gcd(F_n+a,F_{n+1}+a)$?
\end{problem}

\begin{problem}
Theorem \ref{thm3} only gives a necessary but not a sufficient condition for a divisor $d$ of $a^2 \pm 1$ to occur as a greatest common divisor. Theorem \ref{sp3} gives also a sufficient condition for $d=a^2 \pm 1$ to occur as a greatest common divisor. Are there any sufficient conditions for $d \neq a^2 \pm 1$?
\end{problem}

\begin{problem}
Let $a \in \mathbb{Z}$ with $\abs{a} \geq 2$. Since $G_0(a) \subset D(a^2+1)$ and $G_1(a) \subset D(a^2-1)$, we have $\abs{G_0(a)} \leq \tau(a^2+1)$ and $\abs{G_1(a)} \leq \tau(a^2-1)$ (where $\tau(n) = \sum_{d|n} 1$ denotes the divisor function). What are the (exact or asymptotic) sizes of $G_0(a)$ and $G_1(a)$?
\end{problem}

\begin{thebibliography}{9}
\bibitem {chen} K.-W. Chen, Greatest common divisors in shifted Fibonacci sequences, \textit{J. Integer Sequences} \textbf{14} (2011), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL14/Chen/chen70.html}{Article 11.4.7}.

\bibitem {dudtuck} U. Dudley and B. Tucker, Greatest common divisors in altered Fibonacci sequences, \textit{Fibonacci Quart.} \textbf{9} (1971), 89--91.

\bibitem {koshy} T. Koshy, \textit{Fibonacci and Lucas Numbers With Applications}, Wiley-Interscience, 2001.

\bibitem {spilker} J. Spilker, The gcd of the shifted Fibonacci
sequence, in J\"urgen Sander, J\"orn Steuding, and Rasa Steuding, eds.,
\textit{From Arithmetic to Zeta-Functions}, Springer, 2016,
pp.~473--483.

\bibitem {wall} D. D. Wall, Fibonacci series modulo $m$, \textit{Amer.
Math. Monthly} \textbf{67} (1960), 525--532.

\end{thebibliography}


\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } 
shifted Fibonacci sequence, greatest common divisor.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000045}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 31 2018;
revised version received June 20 2018. 
Published in {\it Journal of Integer Sequences}, August 22 2018.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                




.