2$, all prime factors of $p+\varepsilon$ are less than $p$ so, by the induction hypothesis, $k(p+\varepsilon)\in S$ for some $k$. If $p\mid k$ then $p\in\mathcal P_S$. If $p\nmid k$ then, using (\ref{E-prod}), we have $$ u_{pk(p+\varepsilon)}=u_p^{(k(p+\varepsilon))}u_{k(p+\varepsilon)}=u_{pk}^{(p+\varepsilon)}u_{p+\varepsilon}, $$ so that $pk(p+\varepsilon)\in S$, $p\in\mathcal P_S$. This proves the induction step. \end{proof} This completes the proof of Theorem \ref{infinite}. We now consider the finiteness (or otherwise) of $T$ and $\mathcal P_T$. \begin{theorem} [{{Somer \cite[Theorems 8 and 9]{MR1393479}}}]\label{T-finite} The set $T$ is finite in the following two cases: \begin{itemize} \item $P=\pm 1$, $Q\not\equiv -1\pmod{6}$, in which case $T=\{1\}$; \item $P=\varepsilon_1 2^k$, $Q=2^{2k-1}+\varepsilon_2$, where $k$ is a positive integer, and $\varepsilon_1$, $\varepsilon_2\in\{-1,1\}$, in which case $T=\{1,2\}$. \end{itemize} Otherwise, $T$ is infinite. For $T$ infinite, $\mathcal P_T$ is finite precisely when $P,Q$ are not both $0$ and either \begin{itemize} \item $P^2=Q$, in which case $\mathcal P_T$ is the set of prime divisors of $2P$ or \item $P^2=4Q$ or $Q=0$, in which case $\mathcal P_T$ is the set of prime divisors of $P$. \end{itemize} Otherwise, for $T$ infinite, $\mathcal P_T$ is also infinite. \end{theorem} \begin{proof} If $T$ contains an integer $n$ having an odd prime factor $p$ then, by Theorem \ref{T-Basic}(a), $p^kn\in T$ for all $k\ge 0$. In particular, if $P=\pm 1$ and $Q\equiv -1\pmod{6}$, then $6\in T$, so that $T$ is infinite. On the other hand, if $P=\pm 1$ and $Q\not\equiv -1\pmod{6}$, then $1$ is the only basic element of $T$, and $v_1=P$ has no prime factors so that, by Theorem \ref{T-Basic}(a), $\mathcal P_{T,1}$ is empty, and hence $T=\{1\}$. Again starting with $1\in T$, we see that $T$ is infinite if $P$ has any odd prime factors. Also, $T$ is infinite if $P$ is $\pm$ a positive power of $2$ and $2$ is special, as then $2^k\in T$ for all $k\ge 0$, by Theorem \ref{T-Basic}(a). It therefore remains only to consider the case of $P=\pm 2^k$, $k\ge 1$ and $Q$ odd, so that $2$ is not special. Then $2\in T$ and $4\notin T$, by Theorem \ref{T-Basic}(a). If $v_2$ has an odd prime factor $p$, then $2p^k\in T$ for all $k\ge 0$, so that $T$ is again infinite. Finally, if $v_2$ is $\pm$ a power of $2$, then $T=\{1,2\}$. This happens only when $v_2=2^{2k}-2Q=\pm 2$, so that $Q=2^{2k-1}\mp 1$, as claimed. Now take $T$ infinite, with $P,Q$ not both $0$. If the sequence $(v_n)$ is degenerate, then, using Somer \cite[Theorem 9]{MR1393479}, we get either $P^2=Q$, $P^2=4Q$ or $Q=0$, and $\mathcal P_T$ being the set of prime divisors of $P$, as required. On the other hand, if $(v_n)$ is not degenerate then by Somer \cite[Theorem 1]{MR1393479} for sufficiently large $n$ every $v_n$ has a primitive prime divisor. Hence we can find an infinite sequence of numbers $n$ in $T$ such that $np$ is again in $T$, where $p$ is a primitive prime divisor of $v_n$. (Here we are using Theorem \ref{T-Basic}(a).) Thus $\mathcal P_T$ then contains infinitely many primes $p$. \end{proof} \section{The sets $\mathcal P_S$ and $\mathcal P_T$.}\label{S-pspt} From the proof of Theorem \ref{infinite} we see that $\mathcal P_S=\mathcal P_{\operatorname{1st}}$ for $(u_n)$ degenerate or all primes being regular. Our next result takes care of the remaining cases. I thank Larry Somer and the referee for pointing out how the proof of this could be completed. \begin{prop} If $(u_n)$ is nondegenerate and there are irregular primes, then $\mathcal P_S$ is a proper subset of $\mathcal P_{\operatorname{1st}}$. \end{prop} \begin{proof} Take $(u_n)$ nondegenerate and having an irregular prime $f$. Then, from the discussion preceding Proposition \ref{P-allprimes}, every $u_n$ for $n$ sufficiently large has a primitive prime divisor. Indeed, if $\gcd(P,Q)=1$ this is true for $n>30$. Hence for $\ell$ sufficiently large, $u_{\ell f}$ has a primitive prime divisor, $p$ say, so that $\omega(p) = \ell f$. Then if, for some $k$, $kp$ were in $S$, we would have $kp\mid u_{kp}$, so that, by \cite[Proposition 1(iv)]{MR1271392}, $\omega(p)$, and hence $f$, would divide $kp$. Hence $f$ would divide $u_n$, contradicting Corollary \ref{C-reg}. Thus $p\not\in\mathcal P_S$. \end{proof} We have in fact shown that no prime whose rank of appearance is a multiple of any irregular prime $f$ will belong to $\mathcal P_S$. The referee has remarked that, when $\al/\be$ is rational, the density of such primes has been precisely computed in many cases. For $f>2$ and $\al/\be$ not an $f$-th power, it is $f/(f^2-1)$. See Ballot \cite[Theorem 3.2.3]{MR1257079} and also Moree \cite{MR2274151}. Using a similar method, we can also prove the corresponding result for $T$. \begin{prop}\label{P-ptp2nd} The set $\mathcal P_T$ is a proper subset of $\mathcal P_{\operatorname{2nd}}$. \end{prop} \begin{proof} Let $f$ be a primitive prime divisor of $u_n$ for some odd $n$ with $f\nmid 2Q$. Then, by Proposition \ref{P-p|v_n}, $f\in\mathcal P_{\operatorname{1st}}\setminus\mathcal P_{\operatorname{2nd}}$. Now, taking $\ell$ sufficiently large, let $p$ be a primitive prime divisor of $u_{2\ell f}$. Then, as $u_{2\ell f}=u_{\ell f}v_{\ell f}$, $p\mid v_{\ell f}$. Suppose $p\in\mathcal P_T$, so that, for some $k$, $kp\in T$, and hence $kp\mid v_{kp}$. But then by Somer \cite[Proposition 2(vii)]{MR1393479}, $kp$ is a multiple of $\ell f$. In particular, $f\mid v_{kp}$, contradicting $f\not\in\mathcal P_{\operatorname{2nd}}$. So $p\not\in\mathcal P_T$. \end{proof} \section{Divisibility properties of $S$ and of $T$.} \label{S-divisibility} From Theorem \ref{S-Basic} we can consider $S$ as a graph spanned by a forest of one or two trees, with each node corresponding to an element of $S$, and the root nodes of the trees being $\{1\}$, $\{1,6\}$ or $\{1,12\}$. Each edge can be labelled $p$; it rises from a node $n\in S$ to a node $np\in S$, where $p$ is some prime divisor of $u_n\Delta$. One spanning forest is obtained by taking only the edges $n\to np$, where $p$ is the largest prime factor of $np$ such that $n\in S$. (By Theorem \ref{S-down} and Proposition \ref{P-2ell3}, $p$ is either $p_{\max\nolimits}$ or $2$). Thus every node above $n$ in the tree is divisible by $n$. Next, call a {\it cutset} of the forest a set $C$ of nodes with the property that every path from a root to infinity must contain some vertex of the cutset. Then we clearly have the following. \begin{prop} For a cutset $C$ of $S$, every element of $S$ either lies below $C$, or it is divisible by some node of $C$. \end{prop} Judicious choice of a cutset places severe divisibility restrictions on elements of $S$, and so, using this, one can search for elements of $S$ up to a given bound very efficiently. The same argument applies equally to $T$, using Theorem \ref{T-Basic}, with $p$ being either an odd prime divisor of $v_n$ or, under the conditions described in that theorem, the prime $2$. For instance, applying this idea to the sequence $T$ of example 2 below, every element of that sequence except $1$, $3$, $9$, $27$ and $81$ is divisible either by 171 or 243 or 13203 or 2354697 or 10970073 or 22032887841. See \cite{BS} for details. \section{Examples}\label{S-Ex} \begin{enumerate} \item[1.] $P=1,Q=-1$ (the classical Fibonacci and Lucas numbers.) Here $\Delta=5$, $$ S=1, 5, 12, 24, 25, 36, 48, 60, 72, 96, 108, 120, 125, 144, 168, 180,\dots , $$ with $1$ and $12$ basic (\seqnum{A023172} in Neil Sloane's {\it Encyclopedia}), while $\mathcal P_S$ is the whole of $\mathcal P$ (see Theorem \ref{infinite}), $$ T=1, 6, 18, 54, 162, 486, 1458, 1926, 4374, 5778, 13122, 17334, \dots, $$ with $1$ and $6$ basic (\seqnum{A016089}), and $$ \mathcal P_{\text{2nd}} =2, 3, 7, 11, 19, 23, 29, 31, 41, 43, 47, 59, 67, 71, 79, 83, 101, 103, 107, 127,\dots, $$ (A140409) of which $\mathcal P_T$ is a subsequence: $$ \mathcal P_T=2, 3, 107, 1283, 8747, 21401, 34667, 46187,\dots, $$ (A129729). \item[2.] $P=3, Q=2$, where $u_n=2^n-1$, $v_n=2^n+1$. Here $S=\{1\}$ as $\Delta=1$, and $$ T=1, 3, 9, 27, 81, 171, 243, 513, 729, 1539, 2187, 3249,\dots, $$ with $1$ basic (\seqnum{A006521}). Also $$ \mathcal P_{\text{2nd}} =3, 5, 11, 13, 17, 19, 29, 37, 41, 43, 53, 59, 61, 67, 83, 97, 101, 107, 109,\dots, $$ (\seqnum{A014662} -- see also \seqnum{A091317}), of which $$ \mathcal P_T=3, 19, 163, 571, 1459, 8803, 9137, 17497, 41113, \dots $$ (\seqnum{A057719}) is a subsequence. Note too that, by Proposition \ref{P-AJ} and the fact that all $n\in T$ are odd, we have $T=S(-1,-2)$. Also $S=T(-1,-2)=\{1\}$. \item[3.] $P=3$, $Q=5$, $\Delta=-11$, $$ S=1, 6, 11, 12, 18, 24, 36, 48, 54, 66, 72, 96, 108, 121, 132, 144, 162, 168, 192, 198,\dots $$ with $1$ and $6$ basic, with $\mathcal P_{\operatorname{1st}}$ consisting of all primes except the irregular prime $5$, and $$ \mathcal P_S= 2, 3, 7, 11, 13, 17, 23, 37, 41, 43, 67, 71, 73, 83, 89, 97, 101, 103, 107, 113, \dots . $$ Also $$ T=1, 3, 9, 27, 81, 153, 243, 459, 729, 1377, 2187, 2601, 4131, 4401, 6561, 7803, \dots $$ with only $1$ basic, $$ \mathcal P_{\operatorname{2nd}} = 2, 3, 7, 13, 17, 19, 23, 37, 43, 47, 53, 67, 73, 79, 83, 97, 103, 107, 113, \dots $$ and $$ \mathcal P_T = 2, 3, 17, 103, 163, 373, 487, 1733,\dots . $$ \end{enumerate} \section{Additional remarks.}\label{S-final} \begin{enumerate} \item[1.] It would be interesting to see whether the analysis of the paper could be extended to other second-order recurrence sequences, or indeed to any recurrences of higher order. \item[2.] In \cite{BS}, what we called `primitive' solutions of $n\mid 2^n+1$ should in fact have been called {\it fundamental} solutions, following Jarden \cite[p.\ 70]{MR0197383} and Somer \cite[p.\ 522]{MR1271392}, \cite[p.\ 482]{MR1393479}. However, this definition has been superseded by the notion of a basic element (of $S$ or of $T$) as in this paper. \item[3.] In example 1 of Section \ref{S-Ex} above we have $24$ and $25\in S=S(1,-1)$. Are these the only consecutive integers in $S(1,-1)$? \end{enumerate} \section{Acknowledgements} I am very grateful to both Larry Somer and the referee for their detailed contructive comments on an earlier version of this paper. Also, I thank Joe Silverman for a helpful comment. \begin{thebibliography}{10} \bibitem{MR2289425} Mourad Abouzaid, Les nombres de {L}ucas et {L}ehmer sans diviseur primitif, \emph{J. Th\'eor. Nombres Bordeaux} \textbf{18} (2006), 299--313. \bibitem{MR1131414} Richard Andr{\'e}-Jeannin, Divisibility of generalized {F}ibonacci and {L}ucas numbers by their subscripts, \emph{Fibonacci Quart.} \textbf{29} (1991), 364--366. \bibitem{BS} Toby Bailey and Chris Smyth, Primitive solutions of $n\mid 2^n+1$, 2pp., linked from \newline{\tt http://www.research.att.com/$\sim$njas/sequences/A006521}, 2008. \bibitem{MR1257079} Christian Ballot, Density of prime divisors of linear recurrences, \emph{Mem. Amer. Math. Soc.} \textbf{115} (1995), no.~551, 102pp. \bibitem{MR1863855} Yu. Bilu, G.~Hanrot, and P.~M. Voutier, Existence of primitive divisors of {L}ucas and {L}ehmer numbers, \emph{J. Reine Angew. Math.} \textbf{539} (2001), 75--122. \bibitem{MR1516755} R.~D. Carmichael, Note on a recent problem in the {A}merican {M}athematical {M}onthly, \emph{Amer. Math. Monthly} \textbf{14} (1907), 8--9. \bibitem{MR1502458} R. D. Carmichael, On the numerical factors of the arithmetic forms {$\alpha\sp n\pm\beta\sp n$}, \emph{Ann. of Math.} (2) \textbf{15} (1913/14), 30--70. \bibitem{MR0245499} Leonard~Eugene Dickson, \emph{History of the Theory of Numbers. {V}ol. {I}: {D}ivisibility and primality.}, Chelsea Publishing Co., New York, 1966. \bibitem{MR1990179} Graham Everest, Alf van~der Poorten, Igor Shparlinski, and Thomas Ward, \emph{Recurrence Sequences}, Mathematical Surveys and Monographs, vol. 104, American Mathematical Society, Providence, RI, 2003. \bibitem{G} K\'alm\'an Gy\H ory, Az $a^n\pm b^n$ alak\'u sz\'amok oszt\'oir\'ol k\'et sz\'amelm\'eleti feladat kapcs\'an [On divisors of numbers of the form $a^n\pm b^n$], \emph{K\"oz\'episkolai Matematikai Lapok} [Mathematical Journal for Secondary Schools] \textbf{41} (1991), 193--201. \bibitem{GS} K\'alm\'an Gy\H ory and Chris Smyth, The divisibility of $a^n-b^n$ by powers of $n$, to appear. \bibitem{MR0349567} Verner~E. Hoggatt, Jr. and Gerald~E. Bergum, Divisibility and congruence relations, \emph{Fibonacci Quart.} \textbf{12} (1974), 189--195. \bibitem{MR0197383} Dov Jarden, Divisibility of {F}ibonacci and {L}ucas numbers by their subscripts, \emph{Recurring Sequences: {A} Collection of Papers}, Second edition. Revised and enlarged, Riveon Lematematika, Jerusalem (Israel), 1966, pp.~68--75. \bibitem{MR0055373} C.~G. Lekkerkerker, Prime factors of the elements of certain sequences of integers. {I}, {II}, \emph{Nederl. Akad. Wetensch. Proc. Ser. A.} {\textbf 56} =\emph{ Indagationes Math.} \textbf{15} (1953), 265--276, 277--280. \bibitem{MR1505161} Edouard Lucas, Th\'eorie des fonctions num\'eriques simplement p\'eriodiques, \emph{Amer. J. Math.} \textbf{1} (1878), 184--196, 197--240, 289--321. \bibitem{MR2274151} Pieter Moree, On primes {$p$} for which {$d$} divides {${\rm ord}\sb p(g)$}, \emph{Funct. Approx. Comment. Math.} \textbf{33} (2005), 85--95. \bibitem{MR1352481} Paulo Ribenboim, The {F}ibonacci numbers and the {A}rctic {O}cean, \emph{Proceedings of the 2nd {G}auss {S}ymposium. {C}onference {A}: {M}athematics and {T}heoretical {P}hysics} ({M}unich, 1993), Sympos. Gaussiana, de Gruyter, Berlin, 1995, pp.~41--83. \bibitem{MR0139567} Andrzej Schinzel, The intrinsic divisors of {L}ehmer numbers in the case of negative discriminant, \emph{Ark. Mat.} \textbf{4} (1962), 413--416 (1962). \bibitem{MR602235} T.~N. Shorey and C.~L. Stewart, On divisors of {F}ermat, {F}ibonacci, {L}ucas and {L}ehmer numbers. {II}, \emph{J. London Math. Soc.} (2) \textbf{23} (1981), 17--23. \bibitem{MR1271392} Lawrence Somer, Divisibility of terms in {L}ucas sequences by their subscripts, \emph{Applications of {F}ibonacci numbers}, {V}ol. 5 ({S}t. {A}ndrews, 1992), Kluwer Acad. Publ., Dordrecht, 1993, pp.~515--525. \bibitem{MR1393479} Lawrence Somer, Divisibility of terms in {L}ucas sequences of the second kind by their subscripts, \emph{Applications of {F}ibonacci numbers}, {V}ol.\ 6 ({P}ullman, {WA}, 1994), Kluwer Acad. Publ., Dordrecht, 1996, pp.~473--486. \bibitem{MR0491445} C.~L. Stewart, On divisors of {F}ermat, {F}ibonacci, {L}ucas, and {L}ehmer numbers, \emph{Proc. London Math. Soc.} (3) \textbf{35} (1977), 425--447. \bibitem{Wa} Gary Walsh, On integers $n$ with the property $n\mid f_n$, 5pp., unpublished, 1986. \bibitem{MR1632793} Hugh~C. Williams, \emph{\'{E}douard {L}ucas and Primality Testing}, Canadian Mathematical Society Series of Monographs and Advanced Texts, 22, John Wiley \& Sons Inc., New York, 1998, A Wiley-Interscience Publication. \bibitem{Anon} Anonymous Writer, Th\'eor\`emes et probl\`emes sur les nombres, \emph{J. Reine Angew. Math.} \textbf{6} (1830), 100--106. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 11B39. \noindent \emph{Keywords: } Lucas sequences, indices. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A006521}, \seqnum{A014662}, \seqnum{A016089}, \seqnum{A023172}, \seqnum{A057719}, \seqnum{A091317}, \seqnum{A129729}, and \seqnum{A140409}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received August 21 2009; revised version received January 29 2010. Published in {\it Journal of Integer Sequences}, January 31 2010. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}