%\documentstyle[12pt,dina4]{article}
\documentstyle[12pt,dina4]{article}

%Hier stehen einige Definitionen die mathematische Symbole erklaeren
%sie treten nur in mathematischen Umgebungen auf
%                  -----------------------------

%\def\C{{\mathord{\cqchoice{C}{0.65}{0.95}{-0.1}}}}
\def\K{{\mathord{\rm I\mkern-3.6mu K}}}
\def\N{{\mathord{\rm I\mkern-3.6mu N}}}
\def\R{{\mathord{\rm I\mkern-3.6mu R}}}
\def\Z{{\mathord{\rm Z\mkern-5.6mu Z}}}
\def\L{{\mathord{\rm I\mkern-3.6mu L}}}
\def\HH{{\mathord{\rm I\mkern-3.6mu H}}}

%Hier stehen Definitionen, die im Text auftreten

\newcommand{\ala}{\underline}
\newcommand{\fel}{\overline}
\newcommand{\begar}{\begin{array}{l@{\qquad}l}}
\newcommand{\enar}{\end{array}}
%\newtheorem{lemma}{Lemma}
\newtheorem{lemma}{Lemma}[section]
\newenvironment{proof}{{\bf Proof:}}{$\Box$}
\newtheorem{rem}{Remark}
\newtheorem{prop}{Proposition}
\newcommand{\ZK}{{\bf Z_K}}
\newcommand{\KQ}{{\bf K_Q}}
\newcommand{\Q}{{\bf Q}}
\newcommand{\C}{{\bf C}}
\newcommand{\KF}{{\bf K}}
\newtheorem{cor}{Corollary}
%\newtheorem{theorem}{Theorem}
\newtheorem{theorem}{Theorem}[section]
%\newtheorem{feladat}{Feladat}
\newtheorem{feladat}{Feladat}[section]

\begin{document}

\title{ Diophantine properties of linear recursive sequences I}
\author{A. Peth\"o\thanks{ This paper was written when the author 
was a visiting professor at the Mathematical Institute of the Technical 
University of Graz, Austria.
Research partially supported by Hungarian National
Foundation for Scientific Research Grant No 16741/95. }
\\Laboratory of Informatics\\University of Medicine
\\Nagyerdei Krt. 98\\H-4032 Debrecen, Hungary\\
\small e-mail: pethoe@peugeot.dote.hu }
\date{}
\maketitle

\baselineskip=18pt

\section{Introduction and notations}

Let $G_n$ be a $k$-th ($k \ge 2$) order linear recurrence sequence of integers
defined by initial terms $G_0,\dots,G_{k-1} \in \Z$ and by the relation
$$
G_{n+k} = A_1 G_{n+k-1}+ \dots + A_kG_n
$$
for $n \ge 0,$ where $A_1,\dots,A_k \in \Z, \; A_k \not= 0.$ We give in
this note a survey on results concerning the mixed exponential-polynomial
diophantine equation
\begin{equation} \label{1}
G_n = P(x),
\end{equation}
where $P(x) \in \Z[x]$ denotes a polynomial of degree $d \ge 2.$ The ultimate
goal is to find all integers $n,x$ for which (\ref{1}) holds. It is often the
case that, with the currently available methods, we are unable to completely 
solve the problems, though we are usually able to at least obtain an upper
bound for the number of solutions or to prove that the number of solutions is
finite.

In the case $P(x)=0$ there were proven recently very important, general
finiteness theorems about (\ref{1}) by Evertse \cite{Ev1} and by Schlickewei
and van der Poorten \cite{SchP}, moreover Schlickewei \cite{Schl} was able
to give an upper bound for the number of solutions of (\ref{1}). We mention
also that Laurent \cite{L1,L2} and Schlickewei and Schmidt \cite{SchSch}
characterized completely in which cases two linear recurrence sequences  can have
infinitely many common terms. As their method, which is based on the subspace
theorem of W.M. Schmidt \cite{Schm1} seems not applicable if the degree of
$P$ is at least two, we do not go into details, but refer to the survey
paper \cite{EGST} and the book \cite{Schm2}.

After this remark we introduce more notations. Let us denote $C_G(x)=x^k-
A_1 x^{k-1}-\dots -A_k$ the characteristic polynomial of $G_n$ and $\alpha_1,
\dots, \alpha_h$ the distinct zeros of $C_G$ with multiplicities $m_1,\dots,
m_h$ respectively. To exclude discussions of special cases we
assume in the sequel that $G_n$ is {\it non-degenerated}, i.e. if no 
quotients of distinct zeros of its characteristic polynomial are roots of unity.

We will distinguish some sequences which occur frequently in the paper with
special notation. So $F_n$ and $L_n$ will denote the Fibonacci and Lucas
sequences respectively. They are defined by the parameters: $k=2, A_1=A_2=1,
F_0=0,F_1=1$ and $L_0=2, L_1=1.$

In this part of the paper we first show mathematical problems, which lead to 
equations of the form (\ref{1}). Then the most frequently used elementary
methods are discussed. In the second part \cite{P8} we are dealing with 
methods based on lower bounds for linear forms in logarithms of algebraic
numbers. 
 
\section{Is (1) an organic problem?}

In 1984 I gave a lecture in Cologne about perfect powers in second order
linear recurrences after which C. Meyer asked me: 'Is this a generic problem?
Are there mathematical problems which lead to this question?' I was not able
to give him a satisfactory answer.

There are of course diophantine equations which can be transformed more or
less directly to an equation of type (\ref{1}). Consider for example
\begin{equation} \label{3}
a x^{2q} + b x^q y + c y^2 = d,
\end{equation} 
with $a,b,c,d \in \Z$ and such that $b^2-4ac>0$ and not a square. Then we have
to deal with a generalized Pellian equation in unknowns $x^q$ and $y.$ It
is well-known that the solutions of a Pellian equation can be given by terms of
finitely many second order linear recurrence sequences 
and we get equations of the form (\ref{1}). I will
come back to (\ref{3}) in  \cite{P8}. I do not consider this example
a generic one in the sence of C. Meyer.

As far as I know the classical question: 'Are the only squares in the
Fibonacci sequence
$0,1$ and $144$?' appeared at the first time in 1962 in the book of Ogilvy \cite{Og}.
Unfortunately, neither he nor A.P. Rollett, the proposer of problem 5080 in 
the American Mathematical Monthly \cite{Ro} write about its origin. 
J.H.E. Cohn\footnote{e-mail from June 18, 1996} does not know earlier 
references. He heard the problem in a
lecture of Mordell, but thinks that it was of considerable antiquity. The 
problem of Fibonacci squares is a natural, but not a generic one.

In the following I will present examples, which show that (\ref{1}) is indeed a
generic one. The first example is coming from the theory of elliptic curves.
Let $\K$ denote an algebraic number field and consider the set $E(\K)$ of
those $x,y \in \K$ with $y^2 = x^3 + ax +b,$ where $a,b \in \K$ together
with the infinite point $\cal O.$ One can define addition on $E(\K)$, and we
obtain by the Mordell-Weil's theorem a finitely generated Abelian group (see
e.g. \cite{Sil}). An often attacked problem in the theory of elliptic curves is
for a given class of number fields the characterization of the possible
torsion subgroups, i.e. for which integers 
$n$ does there exist $P \in E(\K)$ such that $[n] P = \cal O.$ If $\K$ is a cubic number
field and the $j$-invariant of $E(\K)$ is an algebraic integer, then we proved
with Weis and Zimmer \cite{PWZ,P7}

\begin{theorem}
Let $\K$ be a cubic number field such that there exists over $\K$ an
elliptic curve with integer $j$-invariant and with torsion group isomorphic
to $\Z_5.$ The field $\K$ has this property if and only if  there exist $m,k \in \Z, \; m \ge 0, k \ge -1$ and 
$\varepsilon_2,\varepsilon_3 \in \{ 1,-1 \}$  such that $\K=\Q(\eta),$ where 
$\eta$ is a zero of the polynomial
$$P_3(z;k,m,\varepsilon_2,\varepsilon_3)=z^3+(-12+\varepsilon_2
  5^kG_m)z^2+(10+
\varepsilon_2 \varepsilon_3 5^kG_{m-5\varepsilon_3})z+1,
$$
and $G_m=F_m \; \mbox{or} \; L_m,$ if $k\ge 0$ and $F_{5m},$ if $k=-1.$ 
\end{theorem}

From this theorem it follows that there exist infinitely many elliptic curves
over cubic number fields, which have a torsion group isomorphic to the cyclic
group of five elements. Restricting ourselves to cyclic cubic number fields
the situation 
changes. In this case the discriminant of $P_3(z)$ has to be a square and
we deal with the following diophantine equation:

\begin{equation} \label{5}
D(\varepsilon_2 5^kG_m , \varepsilon_2 \varepsilon_3 5^k G_{m-5
\varepsilon_3}) =\Box
\end{equation} 
where 
\begin{eqnarray*}
 D(u,w) &=& 15125+1464w-3948u-462uw+24w^2 \nonumber \\
& & -24uw^2+244u^2+20u^2w+u^2w^2-4u^3-4w^3.\nonumber
\end{eqnarray*}

Thus, for fixed $k,\varepsilon_2,\varepsilon_3,$ the left hand side of these 
equations are eighth order linear recurrence sequences, which are of course related to the Fibonacci and 
Lucas sequences. Using the methods of sections \ref{Wund} and \ref{Cohn} we
were able to solve these equations completely and proved

\begin{theorem} \label{thpz}
Let $G_m$ be one of the sequences $F_m,L_m,$ if $k \ge 0$ or $F_{5m},$ if 
$k=-1.$ Then the diophantine equation (\ref{5})
has in the integers $k \ge -1, m,y \ge 0$ and $\varepsilon_2,\varepsilon_3
\in \{-1,1\}$ only the solutions\\[2ex]

\begin{tabular}{lccc}
$F_m:$& $(1,0,65,1,1)$&$(1,4,4075,1,-1)$&
$(0,3,163,-1,1)$\\
$L_m:$& $(1,1,520,-1,1)$&$(0,2,63,1,1)$&$(1,2,65,1,1)$\\
$F_{5m}/5:$& $(-1,0,117,1,-1)$&$(-1,5,139,-1,1).$
\end{tabular}
\end{theorem}

Remark that even the finiteness of the number of solutions of equations 
(\ref{5}) does not follow from general results about diophantine equations.

The second example is coming from algebraic number theory. Let $\K$ be an 
algebraic number field of degree $d$ and let us denote by $\Z_{\K}$ its ring of 
integers. It is well known that $\Z_{\K}$ admits always a $\Z$ basis 
$\omega_1=1,\omega_2,\dots,\omega_d,$ but usually the $\omega's$ are not
powers of a fixed element of $\Z_{\K},$ i.e. $\Z_{\K}$ does not have a
power integer basis. For quartic number fields with Galois group $D_4$ we
proved with Ga\'al and Pohst \cite{GPP1,GPP2} that in order to establish all power
integer bases it is enough to find quadratic polynomial values in some
second order linear recurrence sequences. 

\section{Elementary methods}
From now on we shall concentrate on methods for the resolution of equation 
(\ref{1}). To solve a concrete equation, elementary methods are the most frequently
used ones. Relations between sequences, divisibility properties, etc. are
often very useful, but we restrict ourselves  here to dealing with two sieving 
procedures, which we consider the most powerful and  specific elementary tools
in this topic.

\subsection{Wunderlich sieve} \label{Wund}

In order to prove that among the first one million Fibonacci numbers only $0,1$ and $144$
are squares, Wunderlich \cite{Wu} used a sieving procedure. We describe his
method in the more general situation, for equation (\ref{1}). 

We start with a common trick of the theory of diophantine equation: if $n,x
\in \Z$ is a solution of (\ref{1}) then
$$
G_n  \equiv P(x) \pmod{m}
$$
holds for all $m \in \Z.$ For the integer $m$ let us fix a complete residue system.
This consists usually of the absolute smallest or of the smallest positive
residues. It is well known that the sequence ${G_n \bmod m}$ is periodic and if
$(m,A_k)=1$ then it is purely periodic. Let $r_G(m)$ denote the length of 
the minimal period of ${G_n \bmod m}.$ 

Choose integers $m_1,\dots,m_t>0$ with $(m_i,A_k)=1, \; i=1,\dots,t$ and
initialize an array $A[i,j]:=0,\; i=1,\dots,t; \; j=0,\dots, r_G(m_i)-1.$
Compute now for any $i=1,\dots,t$ the numbers $G_n \bmod m_i$ for 
$ n=1,\dots,r_G(m_i)-1$ and $P(x) \bmod m_i $ for $x=0,\dots,m_i-1$ and put
$A[i,j]:=1$ if there exists a $0\le x < m_i$ such that $G_j \equiv P(x) \pmod{m_i}.$
The pair of integers $n,x$ is a solution of (\ref{1}) only if 
$$
A[i, n \bmod m_i]=1
$$
holds for all $i=1,\dots,t .$ By this simple procedure we are able to localize 
the possible solutions in $n$ modulo the least common multiple $R$ of 
$r_G(m_1), \dots r_G(m_t).$

One can considerably increase the performance of the sieving procedure by computing 
first the period lengths for the elements of a large set of integers and choosing only those
as sieving moduli for which the least common multiple of their period length 
is small 
compared to the individual period length. This method was implemented by Nemes 
\cite{N}.

If equation (\ref{1}) has no solution, then one can prove this quickly by 
using the Wunderlich sieve. In \cite{GPP2} we reported about an extensive 
computation, where $13267$ equations of type (\ref{1}) were considered with 
$G_n$ second order linear recurrence sequence and $P(x)$ quadratic polynomials. We got these by 
transforming index form equations of quartic number fields with Galois group 
$D_4$ and discriminants up to $10^6.$ The Wunderlich sieve found
$6595$ cases in which the equations were not solvable.
 
A typical application of the Wunderlich sieve is to prove, with an appropriate choice 
of the set ${\cal M}=\{m_1,\dots,m_t \}$, that all solutions of (\ref{1}) in $n$ belong to some
residue classes mod $R$. Enlarging the set $\cal M$ we can prove the same result
with respect to a larger range. But this process never yields a complete 
solution of (\ref{1}) in the case when it admits a solution
$n \in \Z$, because the elements of the residue class of $n \bmod R$  
always solve (\ref{1}). To completely solve (\ref{1}) in such cases one needs 
either an upper bound for
the possible solutions or one has to combine this method with Cohn's sieve. By 
combining
the Wunderlich sieve with an upper bound for the possible solution, which was 
proved by 
using a lower bound for linear forms in logarithms of algebraic numbers 
I proved that only $0,1$ and $8$ are cubes \cite{P2} and only $0$ and $1$ 
are fifth power Fibonacci numbers \cite{P3}. You may find examples for the 
combination of the sieves
Wunderlich and Cohn in \cite{GPP2} and \cite{P7,PZ}.

I finish this section with a problem:
\bigskip

{\bf Problem:}  
{\it The sequence of tribonacci numbers is defined by $T_0=T_1=0,T_2=1$ and $T_{n+3}=
T_{n+2}+T_{n+1}+T_n$ for $n \ge 0.$ Are the only squares $T_0=T_1=0,T_2=T_3=1, T_5=4,
T_{10}=81,T_{16}=3136=56^2$ and $T_{18}=10609=103^2$ in $T_n$? }

\bigskip

By using the sieving moduli $3,7,11,13,29,41,43,53,79,101,103,131,239,$
$397,421,911,1021$
and $1123$ one can show that this is true for $n \le 2\cdot 10^6,$ but no known
method seem to be applicable for the solution of this problem.

\subsection{Cohn sieve}\label{Cohn}


In this section $\Box$ will denote a square of an integer.
The essential tools of J.E.H. Cohn \cite{Co1} in solving the equations 
$F_n=\Box,2\Box$ and $L_n=\Box,2\Box$ were the following identities:
\begin{eqnarray*}
F_{n+\ell} \equiv -F_{\ell} \pmod{L_{2^{t-1}m}},\\
L_{n+\ell} \equiv -L_{\ell} \pmod{L_{2^{t-1}m}},
\end{eqnarray*}
provided that $n=2^tm$ with $t \ge 2$ and $m \not \equiv 0 \pmod{3}.$ Several 
different generalizations were presented by himself \cite{Co4,Co5}, by 
Ribenboim and McDaniel \cite{RMcD1,RMcD2,RMcD3}, by Ga\'al, Peth\H{o} and Pohst 
\cite{GPP2} and by Peth\H{o}
and Zimmer \cite{PZ}. We cite here a combination of Lemma 1 of  
\cite{RMcD3} and Theorem 3.2 of  \cite{GPP2}. 

In the rest of this section, $U_n=U_n(A_1,A_2),V_n=V_n(A_1,A_2)$ and 
$G_n=G_n(A_1,A_2)$  denote second order linear recurrence sequences  satisfying the same recurrence 
relation with coefficients $A_1,A_2$ and 
with initial terms $U_0=0,U_1=1,V_0=2,V_1=A_1$ and $G_0,G_1 \in \Z$ 
respectively. We assume further that $(A_1,A_2)=1$ and $A_1^2+4 A_2>0.$ We will 
denote by $(a|m)$ the Jacobi symbol. The core of Cohn's sieve is the 
following theorem

\begin{theorem} \label{thCohn}
Let $A_1$ be odd, $n=2^tm$ with $t \ge 1$ and $m\ge 1,$ odd. Then
\begin{equation}
G_{2n+\ell} \equiv -(A_2)^{n}G_{\ell} \pmod{V_n}
\end{equation}
for all $\ell \ge 0.$
\end{theorem}

This is  a combination of Lemma 1 of  \cite{RMcD3} and Theorem 3.2 of  
\cite{GPP2}. Extending Cohn's idea Ribenboim and McDaniel used this theorem 
in the following way: If, for example, for given parameters $A_1$ and $A_2,$ 
$U_n=\Box,$ then the residue class $U_n$ modulo $M$ is a square and therefore
 $(U_n|M)=1$ for any odd $M$ coprime to $U_n.$ They were able to find, for 
 most $n,$ appropriate moduli $M_1,\dots,M_t$ such that the product
$ (U_n|M_1) \cdots (U_n|M_t)=-1,$ leading to contradiction. The remaining 
values of $n$ were treated by using divisibility properties of $U_n.$ They 
proved  \cite{RMcD3}

\begin{theorem}
Let $A_1$ and $A_2$ be odd integers, then
\begin{itemize}
\item[(a)] If $V_n=\Box,$ then $n=1,3$ or $5.$ 
\item[(b)] If $V_n=2\Box,$ then $n=0,3$ or $6.$
\item[(c)] If $U_n=\Box,$ then $n=0,1,2,3,6$ or $12.$
\item[(d)] If $U_n=2\Box,$ then $n=0,3$ or $6.$
\end{itemize}
\end{theorem}

Remark that in \cite{RMcD3} the exceptional cases are completely described. 
Special cases of this theorem were proved in \cite{Co1,Co4,Co5,Co6,Wy}. By 
using A. Baker's method Mignotte and Peth\H{o} 
\cite{MP1} proved that if $U_n(A_1,-1)=d\Box,$ with $d=1,2,3,6$ then 
$n \le 4,$ moreover $U_4(A_1,-1)=d\Box$ only if $A_1=338, U_4(338,-1)=
(2 \cdot 13 \cdot 239)^2.$ In this 
case $A_1$ is arbitrary. Another general result of this sort was found by 
Chen and Voutier \cite{ChV}. By using hypergeometric polynomials they proved: 
Let $d \ge 3$ and $(u,v)$ be the fundamental
solution of the Pell equation $X^2 + 1=dY^2.$ Then the equation $X^2 + 1=dY^4$
has got at most one solution in positive integers. If this solution $(x,y)$ exists,
we have $v=y^2.$ This result implies that if $U_{2t+1}(A_1,1)=\Box$ then
$t=0,$ whenever $A_1>2.$ 

You can find several applications of variations of Theorem \ref{thCohn} in the 
literature. Williams \cite{Wi} determined the Fibonacci numbers of the form 
$\Box +1,$ Robbins \cite{R2} solved the equations $F_n, L_n = w^2-1, w^3 \pm 1;$
Wall \cite{Wa} determined the triangular Fibonacci numbers and Ribenboim and McDaniel  
\cite{Ri,RMcD1} the square classes in the Fibonacci and Lucas sequences and in 
their generalizations. I remark here that using linear forms in logarithms of 
algebraic numbers Kiss \cite{K2}  generalized the latest mentioned result.

\medskip

Theorem \ref{thCohn} can be used successfully to find quadratic polynomial 
values in second order linear recurrence sequences, and more generaly in polynomials of second order
linear recurrence sequences as well. For this purpose the following theorem \cite{PZ} is useful 

\begin{theorem} \label{pz}
 Let $H(x) \in \Z[x],G_n$ an linear recurrence sequence with $|A_2|=1,$ $m_0 \in \Z$ and ${\cal P}= \{ p_1,
\dots,p_t \}$ 
a set of primes with $p_i \ge 5, 1 \le i \le t$. Suppose that there exist positive integers $a,b_1,\dots, b_t$ such that there exist for any $\alpha \ge a-1$ integers 
$\beta_1,\dots,\beta_t$ with $0 \le \beta_i \le b_i \; (i=1,\dots,t)$ for which
 $$
\left(  H(-G_{m_0}) | V_{2^{\alpha}p_1^{\beta_1}\cdots p_t^{\beta_t}} \right) =-1
$$
holds. Then equation 
\begin{equation} \label{8}
H(G_n) = \Box
\end{equation}
has at most one solution $n$ satisfying
$$n \equiv m_0 \; (\mbox{mod} \; 2^{a+1}p_1^{b_1} \cdot  p_t^{b_t}),$$ 
  namely $n=m_0$.
\end{theorem}

This theorem implies the following process which we call Cohn's sieve. Put $M'=H(-G_{m_0})$
and let $M$ be the square free part of $M'.$ For simplicity we assume $M$ to be odd. Let $h$ be a 
positive odd integer, then
$$(M|V_{2^a h})=\pm (V_{2^a h}|M)$$
holds by the reciprocity law of the Jacobi symbol. 

Let now $a$ run through the set of positive integers, then the sequence 
$\{ V_{2^a h} \bmod M \}$ is periodic, thus $\{ (V_{2^a h} | M) \}$ is periodic, too.
Let denote $e(h,M)$ the length of its preperiod and $r(h,M)$ its period respectively. 
It is easy to see that $e(h,M) \le e(1,M)$ holds for all odd $h.$ 

The sieving process is now the following: Choose primes $p_1,\dots , p_t \ge 5$ and set
$$
A[i,j]:= (M|V_{2^jp_i}) \; i=1, \dots ,t ,\; j=1,\dots, e(1,M)+r(p_i,M).
$$
If there exists for any $j> e(1,M)$ an integer $1 \le i \le t$ such that $A[i,j]=-1$ then
 Theorem \ref{pz}
can be applied and we conclude that the only solution of (\ref{8}) with $n 
\equiv m_0 \pmod{2^{e(1,M)+1}p_1\cdots p_t} $ is $m_0.$ If, on the other hand, 
we are able to prove, for example by using the Wunderlich sieve, that (\ref{8}) 
holds only if $n \equiv m_0 \pmod{2^{e(1,M)+1}p_1\cdots p_t}, $ then the 
equation is completely solved. 

\medskip

We illustrate the method by a simple example. Consider the equation
$$
G_n = y^2 +30,
$$
where $G_n$ denotes the sequence defined by $G_0=70,G_1=55, G_{n+2}=3G_{n+1}-G_n$
for $n\ge 0.$ It is clear that $(n,y)=(1,5)$ is a solution, hence we have $m_0=1$ 
and $H(x)=x-30.$ Thus taking $M'=-G_{1}-30=-85,$ which is square-free and 
odd $M=M'.$ 

It is easy to see that the Lucas sequence $\{V_n(3,-1)\}$ associated to $G_n$
has the property: $V_t \equiv -1 \pmod{4}$ for every
$t,$ which is not divisible by $3.$ Let $t$ be such an integer. Then 
$$
(M|V_t) = (-5\cdot 17|V_t) = -(V_t|5)(V_t|17) =(V_t|17),
$$
because $(V_t |5)=-1$ for all $t.$ We also have

\begin{center}
\begin{tabular}{ccrrrrr}
$j$ & $=$ 0 & 1 & 2 & 3 & 4 \\
$(V_{2^j}|17)$ & $=$ -1 & -1 & 1 & -1 & -1 \\
$(V_{5\cdot 2^j}|17)$ & $=$ 1 & -1 & -1 & 1 & -1 
\end{tabular} .
\end{center}

\medskip

The period length of both sequences is three and by Theorem \ref{pz} we obtain 
$n=1$ whenever $n \equiv 1 \pmod{20}.$ On the other hand, $\{G_n-30 \bmod 3\}=
(1,1,2,2)^{\infty}$ and $\{G_n -30 \bmod 7\} = (5,4,2,4)^{\infty},$ thus both 
sequences have period length $4$ and as $(2|3)=(5|7)=-1$ we obtain $n \equiv 1 
\pmod{4},$ hence our equation has got the only solution $n=1.$

Cohn's sieve was implemented at the Lajos Kossuth University by J. Sajtos. By 
using it we were able to solve $5919$ of $7850$ equations of type $G_n = \Box + 
D,$ coming from index form equations over quartic number fields \cite{GPP2}. 
This was also the essential tool, using which we proved Theorem \ref{thpz}, see 
\cite{PZ,P7}. 

Remark that Cohn's sieve does not work always;
an example is presented in section \ref{alg}, but the cases when it fails to work can be
characterized. In \cite{GPP2} it is proved namely, that if there exist integers
$e(1,M) < m_1,m_2 \le e(1,M)+r(1,M)$ such that $(V_{2^{m_1}}|M) (V_{2^{m_2}}|M)=-1,$
then there exists an integer $a \le e(1,M)+r(1,M)+1$ and primes $p_1,\dots , p_t>3$ such that 
equation (\ref{8}) has got at most one solution $n \equiv m_0 \pmod{2^a p_1\cdots p_t},$ namely
$n=m_0.$

%\newpage

\section{Tools from algebraic number theory} \label{alg}

Elementary methods often fail in solving equation of type (\ref{1}). In such 
cases we have to use much involved methods. 
Tools of the theory of algebraic numbers are often helpful to transform 
equations to more simple or more treatable ones. We illustrate this by an 
example, which is taken from de Weger \cite{We2}.

Ray Steiner observed that the eleventh Fibonacci number $89$ has the property
$$
\frac{1}{89} = \sum_{k=0}^{\infty} \frac{F_t}{10^{t+1}}.
$$
He asked de Weger, whether a similar phenomenon occurs for expansions in the base 
$y$ number system of reciprocals of Fibonacci numbers for values of $y$ other 
than $10.$ This is equivalent with the question: for which positive
integers $n,y$ does the identity
$$
\frac{1}{F_n} = \sum_{k=0}^{\infty} \frac{F_t}{y^{t+1}}
$$
hold? One can easily check, that {\it it happens also for $(n,y)=(1,2),(2,2),(5,3)$ 
and $(10,8)$ and de Weger \cite{We2} was able to prove that these are the only 
solutions.} 

What does this problem have to do with diophantine equations? By observing that
$$
\sum_{k=0}^{\infty} \frac{F_t}{y^{t+1}} = \frac{1}{y^2-y-1}
$$
we see that to solve Steiner's problem it is enough to solve the equation
\begin{equation} \label{8a}
F_n = y^2 - y -1.
\end{equation}

Before continuing de Weger's argument we shall point out that for this equation Cohn's sieve 
fails to work because not only $(1,2)$ but also $(-1,1)$ is a solution of 
(\ref{8a}), hence we can not rule out $(1,2)$ by the sieving procedure.

Using the well-known identity $L_n^2 -5 F_n^2 = \pm 4$ we transform (\ref{8a}) to the pair of equations
\begin{equation} \label{9}
 x^2 - 5(y^2 - y -1)^2 = \pm 4.
\end{equation}

Both of the equations (\ref{9}) are quartic elliptic equations. It is well-known (see Mordell \cite{Mo}) that all integer solutions can be obtained from integer solutions of finitely many quartic Thue equations. 
To find these Thue equations we have to work in algebraic number fields. De Weger followed essentially
Mordell's argument, but made use of the special nature of the number fields appearing in the 
transformation. 

After this remark consider first the case of minus sign in (\ref{9}) and observe that
$$
4- 5(y^2 - y -1)^2 = (2- (y^2 - y -1) \sqrt{5})(2+ (y^2 - y -1) \sqrt{5}) = -x^2,
$$
thus we have to work in the algebraic number field $\Q(\sqrt{5}).$ It has got class number $1,$ a 
fundamental unit is $(1+\sqrt{5})/2,$ and $2$ remains prime. A common prime divisor of 
$(2 + (y^2 - y -1) \sqrt{5})$ and $(2- (y^2 - y -1) \sqrt{5})$ can only be $2.$ Thus we obtain
$$
2 + (y^2 - y -1) \sqrt{5} = (-1)^a 2^b \left( \frac{1+\sqrt{5}}{2} \right)^c \alpha^2,
$$
where $a,b,c \in \{0,1 \}, $ and $\alpha$ is an integer in $\Q(\sqrt{5}).$ Assuming $y \ge 2$ 
and since $x$ has to be odd, this implies $a=b=0.$ Finally, since the norm of $2 + (y^2 - y -1) \sqrt{5}$ is $(-1)^c N(\alpha)^2=-x^2,$ we have $c=1.$ Writing $\alpha=(A+B\sqrt{5})/2,$
where the integers $A,B$ have the same parity we obtain
\begin{eqnarray}
A^2 + 10 AB + 5 B^2 &=& 16 \label{10} \\
A^2 + 2 AB + 5 B^2 &=& 8(y^2 - y -1). \nonumber
\end{eqnarray}
Now five times the first equation plus eight times the second equation yields
$$
13 A^2 + 66 AB + 65 B^2 = 16(2 y -1)^2.
$$

Observe that the polynomial staying on the left hand side factors over $\Q(\sqrt{61})$ 
$$
(13 A + 33 B + 2 B \sqrt{61}) (13 A + 33 B - 2 B \sqrt{61}) = 13\cdot 16(2 y -1)^2.
$$
The field $\Q(\sqrt{61})$ has got again class number $1,$ a fundamental unit is $(39 + 5 \sqrt{61})/2,$ the prime $2$ remains prime, and $13$ splits: $13= -((3 + \sqrt{61})/2)
(3 - \sqrt{61})/2)).$ As a common prime divisor of the two factors of the left hand side of the last equation divides $2 \cdot 13 \cdot 61,$ we obtain
$$
13 A + 33 B + 2 B \sqrt{61}= \pm 2^a \left( \frac{3+\sqrt{61}}{2} \right)^b
\left( \frac{3-\sqrt{61}}{2} \right)^c (\sqrt{61})^d \left( \frac{39+ 5\sqrt{61}}{2} \right)^e \alpha^2,
$$
where $a,b,c,d,|e| \in \{0,1 \}, $ and $\alpha$ is an integer in $\Q(\sqrt{61}).$ Taking again norm
we conclude that the only possibilities are $a=d=0,(b,c)=(0,1)$ or $(1,0)$ and $e=\pm 1.$ Thus,
letting $\alpha=(u + v\sqrt{61})$ with integers $u,v,$ we find
\begin{equation} \label{11}
13 A + 33 B + 2 B \sqrt{61}=(47 \pm 6\sqrt{61}) (u + v\sqrt{61}).
\end{equation}

Comparing the coefficients of $1$ and $\sqrt{61}$ we can express $A$ and $B$ as quadratic forms in $u,v.$ The negative sign in (\ref{11}) which corresponds to the case $(b,c,e)=(0,1,1)$ leads to contradiction modulo $13.$ The positive sign can not be ruled out so easily. In that case 
we insert the expressions for $A$ and $B$ into (\ref{10}) and using the transformation $E=v,
F=(u+7v)/2$ we find the Thue equation
$$
E^4 + 2 E^3 F - 41 E^2F^2 -102 E F^3 -59 F^4 = 1.
$$

Similarly, considering the plus sign in (\ref{9}) and working first in the field $\Q(\sqrt{-5})$ and
then in the field $\Q(\sqrt{21})$ we obtain one more non trivial quartic Thue equation to solve,
namely
$$
9E^4 + 18 E^3 F +31 E^2F^2 + 2 E F^3 -11 F^4 = 9.
$$

De Weger finished the solution of Steiner's problem by solving these Thue equations.

\medskip

Remark that for the  solution of  Thue equations there are very efficient methods available. We will not present them here, but refer to the papers \cite{PSch,TdeW,BH}. We also mention that the method of \cite{BH} is
implemented in the computational number theory package KANT, which was developed at the 
TU Berlin by M. Pohst and by his collaborators.

 

\begin{thebibliography}{99}
\bibitem{BH} 
{\sc Yu. Bilu} and {\sc G. Hanrot,} {\em Solving Thue equations of high degree}
J. Number Theory, to appear.
\bibitem{ChV} 
{\sc Chen Jian Hua} and {\sc P.M. Voutier} {\em Complete solution of the 
Diophantine equation $x^2+1 = dY^4,$} J. Number Theory, to appear.
\bibitem{Co1} 
{\sc J.H.E. Cohn,} {\em On square Fibonacci numbers,} J. London Math. Soc. 
{\bf 39} (1964), 537--540.
\bibitem{Co3} 
{\sc J.H.E. Cohn,} {\em Square Fibonacci numbers, etc.} Fibonacci Quart. 
{\bf 2} (1964), 109--113.
\bibitem{Co2} 
{\sc J.H.E. Cohn,} {\em Lucas and Fibonacci numbers and some Diophantine
equations,} Proc. Glasgow Math. Assoc. {\bf 7} (1965), 24--28.
\bibitem{Co4} 
{\sc J.H.E. Cohn,} {\em Eight Diophantine equations,} Proc. London Math. Soc. 
{\bf 16} (1966), 153--166.
\bibitem{Co5} 
{\sc J.H.E. Cohn,} {\em Five Diophantine equations,} Math. Scand. 
{\bf 21} (1967), 61--70.
\bibitem{Co6} 
{\sc J.H.E. Cohn,} {\em Squares in some recurrent sequences,} Pacific
J. Math. {\bf 41} (1972), 631--646.
\bibitem{Co7} 
{\sc J.H.E. Cohn,} {\em The diophantine equation $x^2+C=y^n,$} Acta Arith. 
{\bf 65} (1993), 367--381.
\bibitem{Co8}
{\sc J.H.E. Cohn,} {\em The Diophantine Equation $x^4+1=Dy^2$}, Math. Comp.,
to appear.
\bibitem{Es} 
{\sc A. Eswarathasan,} {\em On square pseudo-Lucas numbers,} Canad. Math.
Bull. {\bf 21} (1978), 297--303.
\bibitem{Ev1}
{\sc J.H. Evertse,} {\em On sums of S-units and linear
recurrences,} Comp. Math. {\bf 53} (1984), 225-244.
\bibitem{EGST}
{\sc J.-H. Evertse, K. Gy\H ory, C. L. Stewart} and {\sc R. Tidjeman,}
{\em $S-$unit equations and their applications} in: New Advances in
Transcendence Theory, Ed: A. Baker, Camb. Univ. Press, Cambridge, 1988.
\bibitem{Fi} 
{\sc R. Finkelstein,} {\em On Fibonacci numbers which are one more than a
square,} J. reine angew. Math. {\bf 262-263} (1973), 171--178.
\bibitem{GPP1} 
{\sc I. Ga\'al, A. Peth\H{o}} and {\sc M. Pohst} {\em On the resolution of 
index form equations in biquadratic number fields} I. J. Number Theory {\bf 38} 
(1991), 18-34. 
\bibitem{GPP2}
{\sc I. Ga\'al, A. Peth\H{o}} and {\sc M. Pohst} {\em On the Resolution of 
Index Form Equations in Dihedral Quartic Number Fields,} Experimental Math. 
{\bf 3} (1994) 245--254. 
\bibitem{K2}
{\sc  P. Kiss,} {\em Pure powers and power classes in recurrence sequences}, 
Math. Slovaca {\bf 44} (1994) 525-529.
\bibitem{L1}
{\sc M. Laurent,} {\em \' Equations exponentielles polyn\^omes
et suites r\' ecurrentes lin\' eaires} Asterisque {\bf 147-148}, (1987)
 121--139.
\bibitem{L2}
{\sc M. Laurent,} {\em \' Equations exponentielles polyn\^omes
et suites r\' ecurrentes lin\' eaires II} J. Number Theory {\bf 31} (1989) 24--53.
\bibitem{LF} 
{\sc H. London} and {\sc R. Finkelstein,} {\em On Fibonacci and Lucas numbers 
which are perfect powers,} Fibonacci Quart. {\bf 7} (1969), 476--481.,
errata {bf 8} (1970), 248.
\bibitem{MP1}
{\sc M. Mignotte} and {\sc A. Peth\H{o},} {\em Sur les carr\'es dans certaines 
suites de Lucas,} Journal de Th\'eorie Nombres de Bordeaux {\bf 5} (1993), 
333-341.
\bibitem{MT}
{\sc M. Mignotte} and {\sc N. Tzanakis,} {\em Arithmetical study of recurrence 
sequences}, Acta Arith. {\bf 57} (1991). 357-364.
\bibitem{Mo} 
{\sc L.J. Mordell,} {\em Diophantine equations}, Academic Press, 1969.
\bibitem{N}
{\sc I. Nemes,} {\em On the solution of the diophantine equation $G_n=P(x)$ with
sieve method}, in Computational Number Theory, Walter de Gruyter, Berlin-New 
York, 1991, pp. 303-311.
\bibitem{Og}
{\sc C.S. Ogilvy,} {\em Tomorrow's math, unsolved problems for the amateur,} 
Oxford Univ. Press, 1962.
\bibitem{P2} 
{\sc A. Peth\H{o},} {\em Full Cubes  in the Fibonacci Sequences,} Publ.  Math. 
Debrecen {\bf 30} (1983), 117-127. 
\bibitem{P3} 
{\sc A. Peth\H{o},} {\em  Perfect Powers in Second Order Recurrences,} 
in: {\em Topics in Classical Number Theory}, Budapest, 1981, 1217-1227. 
\bibitem{P7} 
{\sc A. Peth\H{o},} {\em Systems of norm equations over cubic number fields,} 
Grazer Math. Ber. {\bf 318} (1992), 111--120. 
\bibitem{P8} 
{\sc A. Peth\H{o},} {\em  Diophantine properties of linear recursive sequences II,} 
in preparation.
\bibitem{PSch} 
{\sc A. Peth\H{o}} und {\sc R. Schulenberg} {\em Effektives L\"osen von Thue 
Gleichungen,} Publ. Math. Debrecen {\bf 34} (1987) 189-196.
\bibitem{PW}
{\sc A. Peth\H{o}} and {\sc B.M.M. de Weger,} {\em Product of Prime Powers in 
Binary Recurrence Sequences I.,} Math. Comp. {\bf 47} (1986), 713 -727. 
\bibitem{PWZ}
{\sc A. Peth\H{o}, Th. Weiss} and {\sc H.G. Zimmer}, {\em Torsion groups of 
elliptic curves with integral j-invariant over general cubic number fields,} 
Intern. J. Alg. Comp., to appear.
\bibitem{PZ}
{\sc A. Peth\H{o}} and {\sc H.G. Zimmer}, {\em On a system of norm-equations 
over cyclic cubic number fields,} in preparation.
\bibitem{RMcD1}
{\sc P. Ribenboim} and {\sc W.L. McDaniel,} {\em Square classes of Lucas 
sequences,} Port. Math.  {\bf 48} (1991), 469--473.
\bibitem{RMcD2}
{\sc P. Ribenboim} and {\sc W.L. McDaniel,} {\em Squares and double-squares in
Lucas sequences,} C.R. Math. Rep. Acad. Sci. Canada {\bf 14} (1992), 104--108.
\bibitem{RMcD3}
{\sc P. Ribenboim} and {\sc W.L. McDaniel,} {\em The square terms in Lucas 
sequences,} J. Number Theory  {\bf 58} (1996), 104--123.
\bibitem{Ri} 
{\sc P. Ribenboim,} {\em Square classes of Fibonacci and Lucas numbers,} 
Port. Math. {\bf 46} (1989), 159--175.
\bibitem{R1} 
{\sc N. Robbins,} {\em On Fibonacci numbers which are powers,} Fibonacci Quart. 
{\bf 16} (1978), 515--517.
\bibitem{R2} 
{\sc N. Robbins,} {\em Fibonacci and Lucas numbers of the form $w^2-1,
w^3 \pm 1$,} Fibonacci Quart. {\bf 19} (1981), 369--373.
\bibitem{R3} 
{\sc N. Robbins,} {\em On Fibonacci numbers of the form $px^2$, where $p$
is a prime,} Fibonacci Quart. {\bf 21} (1983), 251--254.
\bibitem{R4}
{\sc N. Robbins,} {\em On Pell numbers of the form $PX^2$, where $P$
is a prime,} Fibonacci Quart. {\bf 22} (1984), 340--348.
\bibitem{Ro}
{\sc A.P. Rollett,} {\em Problem $5080$,} Amer. Math. Monthly {\bf 70} (1963), 216.
\bibitem{Schl} 
{\sc H.P. Schlickewei,} {\em S-unit equations over number fields,} Invent. Math.
{\bf 102} (1990), 95-107.
\bibitem{SchP}
{\sc H.P. Schlickewei and A.J. van der Poorten,}
{\em The growth conditions for recurrence sequences,} Macquarie Univ. Math.
Rep. 82-0041. North Ryde, Australia.
\bibitem{SchSch} 
{\sc H. P. Schlickewei} and {\sc W. M. Schmidt,} {\em Linear
Equations in Members of Recurrence Sequences}
Ann. Scuola Norm. Sup. di Pisa (4) {\bf 20} (1993),  219--246
\bibitem{Schm1} 
{\sc W.M. Schmidt,} {\em Norm form equations,}
Annals of Math. {\bf 96} (1972), 526-551.
\bibitem{Schm2} 
{\sc W.M. Schmidt,} {\em Diophantine Approximations
and Diophantine Equations,} Lecture Notes in Mathematics Vol. 1467, Springer
Verlag, 1991.
\bibitem{ShT} 
{\sc T.N. Shorey} and {\sc R. Tijdeman,} {\em Exponential Diophantine Equations}, 
Cambridge Univ. Press 1986. 
\bibitem{Sil} 
{\sc J. Silverman,} {\em The Arithmetic of Elliptic
Curves,} Graduate Text in Math., Springer Verlag, 1985.
\bibitem{TdeW} 
{\sc N. Tzanakis} and {\sc B.M.M. de Weger,} {\em On the practical solution of 
the Thue equation}, J. Number Theory {\bf 31} (1989) 99-132.
\bibitem{Vo} 
{\sc N.N. Vorobjev,} {\em Fibonacci Numbers} (in Russian), sixth edition,
Nauka Moskau, 1978.
\bibitem{Wa} 
{\sc C.R. Wall,} {\em On the triangular Fibonacci numbers,} Fibonacci Quart. 
{\bf 23} (1985), 77--79.
\bibitem{We1} 
{\sc B.M.M. de Weger,} {\em Algorithms for diophantine equations}, CWI Tract 
Vol. 65. 1989.
\bibitem{We2} 
{\sc B.M.M. de Weger,} {\em A curious property of the eleventh Fibonacci number,} Rocky Mountain J. of Math. {\bf 25} (1995), 977-994.
\bibitem{Wi} 
{\sc H.C. Williams,} {\em On the Fibonacci numbers of the form $k^2+1$, is 
a prime,} Fibonacci Quart. {\bf 13} (1975), 213-214.
\bibitem{WZ} 
{\sc H.C. Williams} and {\sc C.R. Zarnke} {\em Computer solution of the 
Diophantine equation $x^2-dy^4 = -1$}, Proceedings of the Second Manitoba 
Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972), pp. 
405--416. Congressus Numeratium, No.VII, Utilitas Math., Winnipeg, Man., 1973. 
\bibitem{Wo}
{\sc J. Wolfskill,} {\em Bounding squares in second order recurrence sequences}, Acta
Arith. {\bf 54} (1989) 127-145. 
\bibitem{Wu}
{\sc M.C. Wunderlich,} {\em On the existence of Fibonacci squares,} Math. Comp.
{\bf 17} (1963), 455-457.
\bibitem{Wy}
{\sc O. Wyler,} {\em Solution of Problem $5080,$ } Amer. Math. Monthly {\bf 71} (1964),
220-222.
\bibitem{Z} 
{\sc H. G. Zimmer,} {\em Torsion Groups of Elliptic Curves over Cubic and 
Certain Biquadratic Number Fields.} Contemp. Math. {\bf 174}
(1994), 203-220.

\end{thebibliography}

\noindent
AMS Classification Numbers: 11B37, 11D61
\end{document}

