\documentclass[12pt,reqno]{amsart}

\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{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\def\divides{\, | \, }

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

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf The Greatest Common Divisor \\
\ \\
\vskip -.7cm
of Two Recursive Functions \\
}
\vskip 1cm
\large
Jan-Christoph Schlage-Puchta and J{\"u}rgen Spilker\\
Mathematisches Institut\\
Eckerstr.\ 1\\
79104 Freiburg\\
Germany\\
\href{mailto:jcp@math.uni-freiburg.de}{\tt jcp@math.uni-freiburg.de} \\
\href{mailto:Juergen.Spilker@math.uni-freiburg.de}{\tt Juergen.Spilker@math.uni-freiburg.de} \\
\end{center}

\vskip .4 in
\begin{center}
{\bf Abstract}
\end{center}

\vskip .2in

Let $g, h$ be solutions of a linear recurrence relation of length
2. We show that under some mild assumptions the greatest common
divisor of $g(n)$ and $h(n)$ is periodic as a function of $n$ and
compute its mean value. 

\vskip .4in

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

%\usepackage{latexsym}
%\usepackage{amssymb}

%\parskip2ex
%\parindent0pt
%\textheight23cm \textwidth15.6cm \hoffset-1.7cm \voffset-.5cm

\newtheorem{Theo}{Theorem}
\newtheorem{Prop}{Proposition}
\newtheorem{Lem}{Lemma}
\newtheorem{Cor}{Corollary}
\newenvironment{proofof}[1]{\par\noindent{\em {\it Proof of
#1.}}}{\hfill $\square$\par\medskip}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\renewenvironment{proofof}[1]{\par\noindent{\em {\it Proof of #1.}}}{\hfill $\square$\par\medskip}

\section{Problems and Results}
Let $a, b$ be coprime integers, $b\neq 0$, and consider the recurrence
relation 
\begin{equation}\label{RecDef}
f(n+2)=af(n+1)+bf(n), \qquad n\in\N_0.
\end{equation}
Let $g, h:\N_0\to\Z$ be solutions of (\ref{RecDef}) with
\begin{equation}\label{nontriv}
|g(n)|+|h(n)|>0
\end{equation}
for all $n\in\N_0$. We define the gcd function $t(n)=\gcd(g(n),h(n))$ and
consider two problems.

\medskip

\noindent{\bf Problem 1.} Under which conditions on $g$ and $h$ is the function
$t(n)$ periodic? 

\medskip

\noindent {\bf Problem 2.} If $t(n)$ is periodic, what is the mean value of
$t(n)$? 

\medskip

We first need a

\medskip

\noindent {\bf Definition.} We call a function $f:\N_0\to\Z$
periodic and $q\in\N$ a period of $f$, iff there exists some
$n_0\in\N_0$ such that $f(n)=f(n+q)$ for all $n\geq n_0$. If one can
choose $n_0=0$, $f$ is called simply periodic.

\medskip

In this note we prove the following two theorems.

\begin{Theo}
Let $g, h:\N_0\to\Z$ be solutions of (\ref{RecDef}) satisfying
(\ref{nontriv}), and assume that $c:= g(1)h(0)-g(0)h(1)\neq 0$. Then
\begin{enumerate}
\item[(a)] the function $t(n)$ is periodic, moreover, if $\gcd(b, c)=1$, it is
simply periodic;
\item[(b)] every common period of $g(n)\bmod |c|$ and $h(n)\bmod |c|$ is a
period of $t(n)$;
\item[(c)] for all $n\in\N_0$ we have $t(n) \divides c$.
\end{enumerate}
\end{Theo}
\begin{Theo}
Let $g, h:\N_0\to\Z$ be solutions of (\ref{RecDef}) satisfying
(\ref{nontriv}), and assume that $g(0)=0$, $g(1)=1$, $c:=h(0)\neq 0$ and
$\gcd(b, c)=1$. Then
the mean value of $t(n)$equals $\sum_{d\divides c}\frac{\varphi(d)}{k(d)}$, where
$k(d):=\min\{n\in\N: d\divides g(n)\}$.
\end{Theo}

\noindent {\bf Examples.} 1. In the case $g(0)=0$, $g(1)=1$, $h(0)=2$, $h(1)=a$,
McDaniel \cite{McD} has shown, that $t(n)$ is 1 or 2 for
$n\in\N$. This follows also from our Theorem 1 (c). If further
$a=b=1$, we obtain the Fibonacci function (resp., Lucas function). Since
$g(n)\bmod 2$ and $h(n)\bmod 2$ are simply periodic with period 3, we
get 
\[
t(n) = \left\{\begin{array}{ll} 2, & n\equiv 0\pmod{3};\\ 1, &
n\not\equiv 0\pmod{3},\end{array}\right.
\]
with mean value $\frac{4}{3}$. This is a well-known result (see
e.g., \cite{Hog}, \cite{Wal}). 

\medskip

\noindent 2. Defining $g$ and $h$ by $a=1, b=2$, $g(0)=h(0)=1$, $g(1)=2$,
$h(1)=0$, we obtain the gcd function
\[
t(n) = \left\{\begin{array}{ll} 1, & n=0\\ 2, &
n\geq 1\end{array}\right.,
\]
which is periodic, but not simply periodic.

\bigskip

\noindent {\bf Remarks.} 1. The assumption $\gcd(a, b)=1$ in Theorem 1 is necessary,
since for every common divisor $d$ of $a$ and $b$ we have
\[
d^n \divides t(2n), \qquad n\in\N.
\]
If $d>1$, $t(n)$ is unbounded, hence not periodic.

\medskip

\noindent 2. The gcd functions of recurrences of higher order need not be
periodic. The companion polynomial $(x-1)(x-2)(x-3)$ corresponds to
\[
f(n+3)=6f(n+2)-11f(n+1)+6f(n),\qquad n\in\N_0.
\]
It has solutions $g(n)=2^{n+1}-1$ and $h(n)=3^{n+1}-1$ with $c=-2$. If
$p\geq 5$ is a prime, and $n\equiv -1\pmod{p-1}$, then
\[
t(n)=\gcd(2^{n+1}-1, 3^{n+1}-1)\equiv 0\pmod{p}
\]
and $t(n)\geq p$; hence, $t(n)$ is not bounded and a forteriori not
periodic.

\medskip

\noindent 3. The function $\ell(d)$ does not depend on the period $q$ of $t(n)\bmod
d$. If $f(n)$ is the solution of (\ref{RecDef}) with initial values
$f(0)=0, f(1)=1$ (the generalized Fibonacci function), one can take
any period $q$ of $f(n)\bmod d$: We have
\[
g(n)=(g(1)-ag(0))f(n) + g(0)f(n+1), \qquad n\in\N_0,
\]
hence, $q$ is a period of $g(n)\bmod d$, and similarly for $h(n)\bmod
d$, thus $q$ is a period of $t(n)\bmod d$, too.

\medskip

\noindent 4. The mean value $M$ of $t(n)$ depends only on the determinant $c$ of
the initial values of $g$ and $h$. It is unbounded as a function of
$m=|c|$, even if $g(0)=0, g(1)=1$, since $k(d)\leq d4^{\omega(d)}$
(see \cite{Wal}) implies
\[
M\geq
\sum_{d\divides m}\frac{\varphi(d)}{d4^{\omega(d)}}=\prod_{p^j\|m}
\left(1+\frac{p-1}{4p}j\right)\geq\left(\frac{9}{8}\right)^{\omega(m)}
\]

\medskip

\noindent 5. The assumption $\gcd(b, c)=1$ in Theorem 2 is necessary, however, there
is always some $n_0$ such that the function $\tilde{t}(n)=t(n+n_0)$
has the same mean value as $t(n)$ and the mean value formula holds
true for $\tilde{t}$.

\section{Proofs}

We first need two lemmas, which are well-known for the classical
Fibonacci function (see \cite{Hog}).

\begin{Lem}
Let $f:\N_0\to\Z$ be a solution of (\ref{RecDef}), and
$d\in\N$. Then the function $n\mapsto f(n)\bmod d$ is periodic, and
simply periodic if $\gcd(b, d)=1$.
\end{Lem}
\begin{proof}
There are positive integers $n_1<n_2$, such that both $f(n_1)\equiv
f(n_2)\pmod{d}$ and $f(n_1+1)\equiv f(n_2+1)\pmod{d}$. Then
$q=n_2-n_1$ is a period of $f(n)\bmod d$, since by (\ref{RecDef}),
$f(n+q)\equiv f(n)\pmod{d}$ for all $n\geq n_1$. Assume that
$f(n_0+q)\not\equiv f(n_0)\pmod{d}$, and choose $n_0$ maximal with
this property. Then by (\ref{RecDef}), we have $\bmod\; d$ the
congruences 
\begin{eqnarray*}
bf(n_0) & = & f(n_0+2) - af(n_0+1)\\
 & \equiv & f(n_0+q+2) - af(n_0+q+1)\\
 & = & bf(n_0+q).
\end{eqnarray*}
If $\gcd(b, d)=1$, this gives the contradiction $f(n_0)\equiv
f(n_0+q)\pmod{d}$. 
\end{proof}

\begin{Lem}
Let $f:\N_0\to\Z$ be the generalized Fibonacci solution of
(\ref{RecDef}), i.e., $f(0)=0, f(1)=1$. Then
\begin{enumerate}
\item[(a)] $\gcd(f(n), f(n+1))=1, n\in\N_0$;
\item[(b)] $f(m+n)=f(m+1)f(n)+bf(m)f(n-1), m\in\N_0, n\in\N$;
\item[(c)] if $d, n\in\N$, and $k(d)=\min\{n\in\N: d\divides f(n)\}$, then
$\big(d\divides f(n)\Leftrightarrow k(d)\divides n\big)$.
\end{enumerate}
\end{Lem}
\begin{proof}
(a). Let $p$ be a prime, and $n$ be the least integer with $p\divides f(n),
p\divides f(n+1)$; in particular, $n>1$. The equation $f(n+1)=af(n)+bf(n-1)$
implies $p\divides bf(n-1)$, hence, $p\divides b$. Similarly, $f(n)=af(n-1)+bf(n-2)$
implies $p\divides af(n-1)$, thus $p\divides a$.
This contradicts the assumption $\gcd(a, b)=1$.

(b). This follows by induction on $n$.

(c). Let $L:=\{n\in\N_0: d\divides f(n)\}$. If $m, n\in L$, we get $m+n\in L$ by
(b)., and if $m>n$, we have $f(m)=f(m-n)f(n+1)+bf(m-n-1)f(n)$, hence,
$d\divides f(m-n)f(n+1)$, so $m-n\in L$ by (a). Take $n\in L$ and write
$n=mk(d)+t$ with $0\leq t<k(d)$. Since $t=n-mk(d)\in L$, we have $t=0$
and $L=k(d)\cdot\N_0$. This proves the last claim.
\end{proof}

\begin{proofof}{Theorem 1} Let $f:\N_0\to\Z$ be the solution
of (\ref{RecDef}) with initial values $f(0)=0, f(1)=1$. We have
\begin{equation}\label{fconvert1}
cf(n)=h(0)g(n)-g(0)h(n),\qquad n\in\N_0,
\end{equation}
since both sides solve (\ref{RecDef}), and the initial values are 0
and $c$. Similarly,
\begin{equation}\label{fconvert2}
cf(n+1)=(ah(0)-h(1))g(n)-(ag(0)-g(1))h(n),\qquad n\in\N_0.
\end{equation}
Fix $n\in\N_0$ and let $t$ be a common divisor of $g(n)$ and
$h(n)$. Then $t\divides c(f(n), f(n+1))$ by (\ref{fconvert1}) and
(\ref{fconvert2}), hence $t\divides c$ by Lemma 2 (a) From this we deduce
\begin{equation}\label{tresult}
t(n)\divides c, \qquad\mbox{for all }n\in\N_0.
\end{equation}
By Lemma 1, a common period $q$ of $g(n)\bmod |c|$ and $h(n)\bmod |c|$
exists, so, by (\ref{tresult}),
\[
t(n) = \gcd(g(n), h(n), c) = \gcd(g(n+q), h(n+q), c) = t(n+q), \quad \mbox{if }n\geq n_0.
\]
This proves Theorem 1.
\end{proofof}
\begin{proofof}{Theorem 2}
Set $m:=|c|$, and let $q$ be a period of $t(n)\bmod m$, which exists
by Lemma 1. Then, since $t$ is simply periodic, the mean value of
$t(n)$ is 
\[
M = \frac{1}{q}\sum_{1\leq n\leq q} t(n),
\]
and by Theorem 1 (c), this quantity is equal to
$\frac{1}{q}\sum_{d\divides m}d\ell(d)$,
where $\ell(d)=\#\{n\leq q: \gcd(t(n), m)=d\}$. Further,
we have
\[
M = \frac{1}{q}\sum_{1\leq n\leq q} \gcd(t(n), m) = \frac{1}{q}\sum_{s\divides m}s
\left(\sum_{{1\leq n\leq q}\atop{\gcd(t(n), m)=s}}1\right). 
\]
Since
\begin{equation}\label{mu}
\sum_{k\divides n}\mu(k) = \left\{\begin{array}{ll}1, & n=1\\
0, & n>1\end{array}\right.,
\end{equation}
the inner sum can be written as
\[
\sum_{{1\leq n\leq q}\atop{s\divides t(n)}} \sum_{k\divides \gcd(t(n)/s, m/s)}\mu(k) =
\sum_{k\divides \frac{m}{s}}\left(\mu(k)\sum_{{1\leq n\leq q}\atop{sk \divides t(n)}}
1\right).
\]
Set $d:=sk$; then
\[
M=\sum_{d\divides m}\left(\ell(d)\sum_{k\divides d}\mu(k)\frac{d}{k}\right).
\]
We use $\sum_{d\divides n}\varphi(d)=n$ together with $(\ref{mu})$ and see
$\sum_{k\divides d}\mu(k)\frac{d}{k}=\varphi(d)$. Hence,
\[
M = \frac{1}{q}\sum_{d\divides m}\varphi(d)\#\{n\leq q: d\divides t(n)\}
\]
Since $g(0)=0, g(1)=1$, we have
\[
h(n)=(h(1)-ah(0))g(n) + h(0)g(n+1),
\]
and by Lemma 2 (a), we obtain
\[
t(n)=\gcd(g(n), h(0)g(n+1)) = \gcd(g(n), h(0)) = \gcd(g(n), m).
\]
We finally get by Lemma 2 (c) for every $d\divides m$
\[
\#\{n\leq q: d\divides t(n)\} = \sum_{{1\leq n\leq q}\atop{d\divides g(n)}} 1 =
\sum_{{1\leq n\leq q}\atop{k(d)\divides n}} 1 = \frac{q}{k(d)},
\]
and Theorem 2 is proven.
\end{proofof}
\begin{thebibliography}{3}
\bibitem{McD} W. L. McDaniel, The g.c.d in Lucas sequences and Lehmer
number sequences. {\em Fibonacci Quart.} {\bf 29} (1991), 24--29.
\bibitem{Hog} V. E. Hoggatt, {\em Fibonacci and Lucas numbers}, 
Boston etc.: Houghton Mifflin Company IV, 1969.
\bibitem{Wal} D. D. Wall, Fibonacci series modulo $m$, {\em
Amer. Math. Monthly} {\bf 67} (1960), 525--532.
\end{thebibliography}

\bigskip
\hrule
\bigskip

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


\noindent \emph{Keywords: } Greatest common divisor, recursive functions,
periodic functions, mean values.


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 8 2003;
revised version received January 27 2004.  
Published in {\it Journal of Integer Sequences}, February 16 2004.

\bigskip
\hrule
\bigskip

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


\end{document}