\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} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf On Generalized Cullen and Woodall Numbers \\ \vskip .12in That are Also Fibonacci Numbers } \vskip 1cm \large Diego Marques\\ Departamento de Matem\' atica\\ Universidade de Bras\' ilia\\ Bras\' ilia 70910-900 \\ Brazil\\ \href{mailto:diego@mat.unb.br}{\tt diego@mat.unb.br}\\ \end{center} \vskip .2 in \newcommand{\R}{{\mathbb R}} \newcommand{\Q}{{\mathbb Q}} \newcommand{\C}{{\mathbb C}} \newcommand{\N}{{\mathbb N}} \def\noi {\noindent} \def\Ker {{\rm Ker}} \def\Im {{\rm Im}} \def\a {\alpha} \def\m {\mu} \def\g {\gamma} \def\p {\phi} \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\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 {\delta} \def\g {\gamma} \def\l {\lambda} \def\dfrac {\displaystyle\frac } \def\k {\kappa} \begin{abstract} The $m$-th Cullen number $C_m$ is a number of the form $m2^m+1$ and the $m$-th Woodall number $W_m$ has the form $m2^m-1$. In 2003, Luca and St\u anic\u a proved that the largest Fibonacci number in the Cullen sequence is $F_4=3$ and that $F_1=F_2=1$ are the largest Fibonacci numbers in the Woodall sequence. A generalization of these sequences is defined by $C_{m,s}=ms^m+1$ and $W_{m,s}=ms^m-1$, for $s>1$. In this paper, we search for Fibonacci numbers belonging to these generalized Cullen and Woodall sequences. \end{abstract} \section{Introduction}\label{sec1} A {\it Cullen number} is a number of the form $m2^m+1$ (denoted by $C_m$), where $m$ is a nonnegative integer. The first few terms of this sequence are \[ 1, 3, 9, 25, 65, 161, 385, 897, 2049, 4609, 10241, 22529,\ldots \] which is the OEIS \cite{oeis} sequence \seqnum{A002064}. (This sequence was introduced in 1905 by Father Cullen \cite{cul} and it was mentioned in the well-known book of Guy \cite[Section {\bf B20}]{guy}.) These numbers gained great interest in 1976, when Hooley \cite{hoo} showed that almost all Cullen numbers are composite. However, despite their being very scarce, it is still conjectured that there are infinitely many \textit{Cullen primes}. For instance, $C_{6679881}$ is a prime number with more than 2 millions of digits (PrimeGrid, August 2009). In a similar way, a \textit{Woodall number} (also called \textit{Cullen number of the second kind}) is a positive integer of the form $m2^m-1$ (denoted by $W_m$). The first few terms of this sequence are \[ 1, 7, 23, 63, 159, 383, 895, 2047, 4607, 10239,\ldots \] which is the OEIS sequence \seqnum{A003261}. In a personal communication to Keller \cite[p.\ 1739]{new}, Suyama asserted that Hooley's method can be reformulated to show that it works for any sequence of numbers of the form $m2^{m+a} + b$ where $a$ and $b$ are integers. In particular, Woodall numbers are almost all composites. However, it is conjectured that the set of {\it Woodall primes} is infinite. We remark that $W_{3752948}$ is a prime number (PrimeGrid, December 2007). These numbers can be generalized to the \textit{generalized Cullen and Woodall numbers} which are numbers of the form \begin{center} $C_{m,s}=ms^m+1$ and $W_{m,s}=ms^m-1$, \end{center} where $m\geq 1$ and $s\geq 2$. Clearly, one has that $C_{m,2}=C_m$ and $W_{m,2}=W_m$, for all $m\geq 1$. For simplicity, we call $C_{m,s}$ and $W_{m,s}$ an \textit{$s$-Cullen number} and an \textit{$s$-Woodall number}, respectively. Also, an $s$-Cullen or $s$-Woodal number is said to be {\it trivial} if it has the form $s+1$ or $s-1$, respectively, or equivalently when its first index is equal to $1$. This family was introduced by Dubner \cite{dub} and is one of the main sources for prime number ``hunters". A prime of the form $C_{m,s}$ is $C_{139948,151}$ an integer with 304949 digits. Many authors have searched for special properties of Cullen and Woodall numbers and their generalizations. In regards to these numbers, we refer to \cite{pt,uber,new} for primality results and \cite{mdc} for their greatest common divisor. The problem of finding Cullen and Woodall numbers belonging to other known sequences has attracted much attention in the last two decades. We cite \cite{pseudo} for pseudoprime Cullen and Woodall numbers, and \cite{bar} for Cullen numbers which are both Riesel and Sierpi\' nski numbers. In 2003, Luca and St\u anic\u a \cite[Theorem 3]{LS} proved that the largest Fibonacci number in the Cullen sequence is $F_4=3=1\cdot 2^1+1$ and that $F_1=F_2=1=1\cdot 2^1-1$ are the largest Fibonacci numbers in the Woodall sequence. Note that these numbers are trivial Cullen and Woodall numbers (in the previous sense, i.e., $m=1$). In this paper, we search for Fibonacci numbers among $s$-Cullen numbers and $s$-Woodall numbers, for $s>1$. Our main result is the following \begin{theorem}\label{main1} Let $s$ be a positive integer. If $(m,n,\ell)$ is an integer solution of \begin{equation}\label{Main} F_n=ms^{m}+\ell, \end{equation} where $\ell\in \{-1,1\}$ and $m,n>0$, then \begin{equation}\label{ine} m<(6.2 + 1.9P(s))\log (3.1+P(s)), \end{equation} and \[ n<\dfrac{\log ((6.2 + 1.9P(s))\log (3.1+P(s))s^{(6.2 + 1.9P(s))\log (3.1+P(s))}+1)}{\log \alpha}+2, \] where $P(s)$ denotes the largest prime factor of $s$ and $\alpha=(1+\sqrt{5})/2$. \end{theorem} In particular, the above theorem ensures that for any given $s\geq 2$, there are only finitely many Fibonacci numbers which are also $s$-Cullen numbers or $s$-Woodall numbers and they are effectively computable. We should recall that $\nu_p(r)$ denotes the $p$-adic order (or valuation) of $r$ which is the exponent of the highest power of a prime $p$ which divides $r$. Also, the {\it order (\mbox{or} rank) of appearance} of $n$ in the Fibonacci sequence, denoted by $z(n)$, is defined to be the smallest positive integer $k$, such that $n\mid F_k$ (some authors call it \textit{order of apparition}, or \textit{Fibonacci entry point}). We refer the reader to \cite{lucas,d1,d20,d21,d22} for some results about this function. Let $p$ be a prime number and set $e(p):=\nu_p(F_{z(p)})$. By evaluating $e(p)$, for primes $p<30$, one can see that $e(p)=1$. In fact, $e(p)=1$ for all primes $p<2.8\cdot 10^{16}$ (PrimeGrid, March 2014). Moreover, the assertion $e(p)=1$ for all prime $p$ is equivalent to $z(p)\neq z(p^2)$, for all primes $p$ (this is related to Wall's question \cite{wall}). This question raised interest in 1992, when Sun and Sun \cite{SS} proved (in an equivalent form) that $e(p)=1$ for all primes $p$, implies the first case of Fermat's ``last theorem''. In view of the previous discussion, it seems reasonable to consider problems involving primes with $e(p)=1$ (because of their abundance). Our next result deals with this kind of primes. \begin{theorem}\label{main2} There is no integer solution $(m,n,s,\ell)$ for Eq.\ (\ref{Main}) with $n>0$, $m>1$, $\ell\in \{-1,1\}$ and $s>1$ such that $e(p)=1$ for all prime factor $p$ of $s$. \end{theorem} In particular, the only solutions of Eq.\ (\ref{Main}), with the previous conditions, occur when $m=1$ and have the form \[ (m,n,s,\ell)=(1,n,F_n-\ell,\ell). \] An immediate consequence of Theorem \ref{main2} and the fact that $e(p)=1$ for all primes $p<2.8\cdot 10^{16}$ is the following \begin{corollary} There is no Fibonacci number that is also a nontrivial $s$-Cullen number or $s$-Woodall number when the set of prime divisors of $s$ is contained in \[ \{2,3,5,7,11,\ldots,27999999999999971, 27999999999999991\}. \] This is the set of the first $759997990476073$ prime numbers. \end{corollary} Here is an outline of the paper. In Section \ref{aux}, we recall some facts which will be useful in the proofs of our theorems, such as the result concerning the $p$-adic order of $F_n$ and factorizations of the form $F_n\pm 1=F_aL_b$, with $|a-b|\leq 2$. In the last section, we combine these mentioned tools, the fact that a common divisor of $F_a$ and $L_b$ is small and a lower bound for Fibonacci and Lucas numbers, to get an inequality of the form $m16$ (however, for our purpose it suffices to consider $m>4$). We rewrite Eq.\ (\ref{Main}) as $F_n-\ell=ms^{m}$. Since $\ell\in \{-1,1\}$, then Lemma \ref{l2} gives $F_aL_b=ms^{m}$, where $2a,2b\in \{n\pm 2,n\pm 1\}$ and $|a-b|\in \{1,2\}$. Observe that in this case $\gcd(F_a,L_b)=1$ or $3$ (Lemma \ref{l1} (a)). \medskip \indent {\bf Case 1.} If $s\not\equiv 0\pmod 3$. Since $\gcd(F_a,L_b)=1$ or $3$ and $3\nmid s$, then, without loss of any generality, we can write $s=p_1^{a_1}\cdots p_k^{a_k}$, with $a_i\geq 0$, such that $p_1^{a_1}\cdots p_t^{a_t}$ divides $F_a$ and $p_{t+1}^{a_{t+1}}\cdots p_k^{a_k}$ divides $L_{b}$, where $p_1,\ldots,p_k$ are distinct primes. Thus $\nu_{p_i}(F_{a})\geq a_im$, for $i\in [1,t]$ and $\nu_{p_j}(L_b)\geq a_jm$, for $j\in [t+1,k]$, and on the other hand, Lemmas \ref{l3} and \ref{l4} imply \[ \nu_{p_i}(F_{a})\leq \nu_{p_i}(a)+(1-\delta_{{p_i},5}+\delta_{p_i,2})e({p_i}) \] and \[ \nu_{p_j}(L_b)\leq \max\{\nu_{p_j}(b)+e(p_j),2\}, \] where $\delta_{r,s}$ denotes the usual Kronecker delta. Since $1-\delta_{{p_i},5}+\delta_{p_i,2}\leq 2$ and $m>2$, then \begin{center} $\nu_{p_i}(F_{a})\leq \nu_{p_i}(a)+2e({p_i})$ and $\nu_{p_j}(L_{b})\leq \nu_{p_j}(b)+e({p_j})$. \end{center} Thus one obtains that $\nu_{p_i}(a)\geq a_im-2e({p_i})$, for all $i\in [1,t]$ and $\nu_{p_j}(b)\geq a_jm-e(p_j)$, for all $j\in [t+1,k]$. Since $p_1,\ldots,p_k$ are pairwise coprime, we have $a\geq p_1^{a_1m-2e(p_1)}\cdots p_k^{a_km-2e(p_t)}$ and $b\geq p_{t+1}^{a_{t+1}m-e(p_{t+1})}\cdots p_{k}^{a_{k}m-e(p_{k})}$. Hence $F_aL_b=ms^{m}$ together with the estimates in Lemma \ref{l1} (d) yields \begin{eqnarray*} mp_1^{ma_1}\cdots p_k^{ma_k} & \geq & \alpha^{a+b-3}\\ & > & \alpha^{\prod_{i=1}^t p_i^{ma_i-2e(p_i)}+\prod_{i=t+1}^k p_i^{ma_i-2e(p_i)}-3}, \end{eqnarray*} where we used the inequality $ma_i-e(p_i)>ma_i-2e(p_i)$. Note that we may suppose that $ma_i>2e(p_i)$, for all $i\in [1,k]$ (otherwise, we would have $m\leq 2e(p_i)$, for some $i$ and Theorem \ref{main1} is proved). Also $p_i\geq 2$, for all $i\in [1,k]$ and then \[ \displaystyle\prod_{i=1}^t p_i^{ma_i-2e(p_i)}+\displaystyle\prod_{i=t+1}^k p_i^{ma_i-2e(p_i)}\geq \displaystyle\sum_{i=1}^kp_i^{ma_i-2e(p_i)}. \] Thus we have \[ 4.3mp_1^{ma_1}\cdots p_k^{ma_k} > \alpha^{p_1^{ma_1-2e(p_1)}}\cdots \alpha^{p_k^{ma_k-2e(p_k)}}, \] where we have used that $\alpha^3<4.3$. But for $m>4$, it holds that $4.3m<2^m\leq p_1^{m}$ and so \[ p_1^{m(a_1+1)}\cdots p_k^{ma_k} > \alpha^{p_1^{ma_1-2e(p_1)}}\cdots \alpha^{p_k^{ma_k-2e(p_k)}}. \] If the inequality $p_i^{ma_i-2e(p_i)}>m(a_i+1)(\log p_i)/\log \alpha$ holds for all $i\in [1,k]$, we arrive at the following absurdity \[ p_1^{m(a_1+1)}\cdots p_k^{ma_k}>\alpha^{p_1^{ma_1-2e(p_1)}}\cdots \alpha^{p_k^{ma_k-2e(p_k)}}>p_1^{m(a_1+1)}\cdots p_k^{m(a_k+1)}. \] Thus, there exists $i\in [1,k]$, such that $p_i^{ma_i-2e(p_i)}\leq m(a_i+1)(\log p_i)/\log \alpha$. Now, by applying the $\log$ function in the previous inequality together with a straightforward calculation, we obtain \[ \dfrac{m}{\log m}\leq \dfrac{1}{\log p_i}+\dfrac{\log (a_i+1)}{a_i\log m\log p_i}+\dfrac{\log \left(\frac{\log p_i}{\log \alpha}\right)}{a_i\log m\log p_i}+\dfrac{2e(p_i)}{a_i\log m}. \] Note that $a_i\geq 1$, $\log p_i\geq \log 2>0.69$ and $\log m\geq \log 3>1.09$. Also, the functions $x\mapsto (\log(x+1))/x$ and $x\mapsto (\log(\log x/\log \alpha))/(\log x)$ are nonincreasing for $x\geq 1$ and $x\geq 4$, respectively, then $(\log (a_i+1))/a_i\leq \log 2$ and $(\log(\log p_i/\log \alpha))/(\log p_i)<0.77$. Therefore, \[ \dfrac{m}{\log m}<3.1+1.9e(p_i). \] Since the function $x\mapsto x/\log x$ is increasing for $x>e$, it is a simple matter to prove that, for $A>e$, \begin{equation}\label{tutu} \dfrac{x}{\log x}e$, we have that \begin{equation}\label{key} m<(6.2+3.8e(p_i))\log (3.1+1.9e(p_i)). \end{equation} Since $p_i\leq P(s)$, then in order to get the desired inequality in (\ref{ine}), it suffices to prove that $e(p)\leq p/2$ for all primes $p$. Clearly, the inequality holds for $p=2$, so we may suppose $p\geq 3$. Since $p^{e(p)}\mid F_{z(p)}$, we have $p^{e(p)}\leq F_{z(p)}$. Suppose, towards a contradiction, that $e(p)> p/2$, then we use Lemma \ref{l1} (d) and (e) to obtain \[ p^{p/2}< p^{e(p)}\leq F_{z(p)}\leq \alpha^{z(p)-1}\leq \alpha^p. \] This yields that $p< \alpha^2<2.619$ which is impossible, since $p\geq 3$. Thus $e(p)\leq p/2$ \footnote{In fact, the same proof gives the sharper bound $e(p)\leq (p\log \alpha)/\log p$. This bound together with the squeeze theorem gives $\displaystyle\lim_{p\to \infty}e(p)/p=0.$}. Thus \[ m<(6.2 + 1.9P(s))\log (3.1+P(s)), \] where we used that $P(s)\geq p_i$, for all $i\in [1,k]$. Now, we use Lemma \ref{l1} (d) to get $\alpha^{n-2}\leq F_n\leq ms^{m}+1$ and a straightforward calculation yields \[ n<\dfrac{\log ((6.2 + 1.9P(s))\log (3.1+P(s))s^{(6.2 + 1.9P(s))\log (3.1+P(s))}+1)}{\log \alpha}+2, \] where we used the upper bound for $m$ in terms of $s$. \medskip \indent {\bf Case 2.} If $s\equiv 0\pmod 3$. We can proceed as before unless $\gcd(F_a,L_{b})=3$. In this case, for some suitable choice of $\e_1,\e_2\in \{0,1\}$, with $\e_1+\e_2=1$, we have \[ \dfrac{F_a}{3^{\e_1}}\cdot \dfrac{L_b}{3^{\e_2}}=\dfrac{ms^m}{3} \] and $\gcd(F_a/3^{\e_1},L_b/3^{\e_2})=1$. From this point on the proof proceeds along the same lines as the proof of previous case. \qed \subsection{The proof of Theorem \ref{main2}} Let $(m,n,s,\ell)$ be a solution of Eq.\ (\ref{Main}) satisfying the conditions in the statement of Theorem \ref{main2} and suppose that $m\leq 16$. Note that $F_n=4s^4\pm 1$ can be rewritten as $F_n=(2s^2)^2\pm 1$, but Bugeaud et al. \cite[Theorem 2]{bugeaud} listed all solutions of the Diophantine equation $F_n\pm 1=y^t$. A quick inspection in their list gives $y=1,2$ or $3$, but none of these values have the form $2s^2$, for $s>1$. So, there is no solution for Eq.\ (\ref{Main}) when $m=4$. So, we wish to solve the equation $F_n=ms^m\pm 1$, when $m\in [2,16]\backslash \{4\}$. As previously done, let us rewrite it as $F_aL_b=ms^m$. Note that $m$ has at most $2$ distinct prime factors and they belong to $\{2,3,5,7,11,13\}$. Since $\gcd(F_a,L_b)=1$ or $3$, we can deduce that \begin{equation}\label{small} F_a=p_1^{\a_1}p_2^{\a_2}p_3^{\a_3}(s_1^{r})^p, \end{equation} where $p_1,p_2,p_3,p$ are primes less than $17$, $\a_1,\a_2,\a_3\in \{0,1,2,3,4\},\ s_1\mid s$ and $m=pr$. However, in 2007, by combining some deep tools in number theory, Bugeaud, Luca, Mignotte and Siksek \cite[Theorem 4 for $m=1$]{siksek}, found (in particular) all solutions of the Diophantine equation \[ F_t=2^{x_1}\cdot 3^{x_2}\cdots 541^{x_{100}}y^p, \] where $x_i\geq 0$ and $p$ is a prime number. More precisely, they proved that in this case, one has \begin{equation}\label{pos} t\in [1,16]\cup [19,22]\cup \{24,26,27,28,30,36,42,44\}. \end{equation} In particular, $t\leq 44$. Note that Eq.\ (\ref{small}) is a particular case already treated by Theorem 4 of \cite{siksek}. However, for convenience of the reader, we describe in a few words how these calculations can be performed. First, if $m=2$, then we have the equation $F_a=2^{\a_1}\cdot 3^{\a_2}s_1^2$ and after a quick inspection in (\ref{pos}), one can see that possible values for $a$ do not give any solution for Eq.\ (\ref{Main}). In the case of $m\geq 3$, we use that $a\leq 44$ together with $a\geq (n-2)/2$ to get $n\leq 90$ and so \[ 3s^3-1\leq ms^m+\ell=F_n\leq F_{90}=2880067194370816120. \] Therefore $s\leq 986492$. Now by using {\it Mathematica} \cite{math}, one deduces that the Diophantine equation $F_n=ms^m+\ell$, for $2\leq n\leq 90$, $3\leq m\leq 16$, $\ell\in \{-1,1\}$ and $2\leq s\leq 986492$, has no any solution. Let us suppose that $m>16$. We remark that in order to get the inequality (\ref{key}) in the proof of Theorem \ref{main1}, we only assume that $m>4$. Thus, we have \[ m<(6.2+3.8e(p_i))\log (3.1+1.9e(p_i)), \] where $p_i$ is a prime factor of $s$. However, by hypothesis, all prime factors $p$ of $s$ satisfy $e(p)=1$. In particular, $e(p_i)=1$ and so we have the following absurdity: $16