\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}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{definition}[theorem]{Definition} \begin{center} \vskip 1cm{\LARGE\bf Cipolla Pseudoprimes} \vskip 1cm \large Y. Hamahata\footnote{Partially supported by Grant-in-Aid for Scientific Research (No.\ 18540050), Japan Society for the Promotion of Science.} and Y. Kokubun\\ Department of Mathematics \\ Tokyo University of Science \\ Noda, Chiba, 278-8510 \\ Japan \\ {\tt hamahata\_yoshinori@ma.noda.tus.ac.jp}\\ \end{center} \vskip .2in \begin{abstract} We consider the pseudoprimes that M. Cipolla constructed. We call such pseudoprimes {\it Cipolla pseudoprimes}. In this paper we find infinitely many Lucas and Lehmer pseudoprimes that are analogous to Cipolla pseudoprimes. \end{abstract} \section{Introduction} Take an integer $a>1$. A {\it pseudoprime to base} $a$ is a composite number $n$ such that $a^{n-1}\equiv 1\, (\bmod\, n)$. In 1904, M. Cipolla \cite{Cipolla} found infinitely many pseudoprimes to a given base $a$. To be more precise, \begin{theorem}[Cipolla \cite{Cipolla}, cf.\ Ribenboim \cite{Ribenboim1}]\label{1} Let $p$ be a prime such that $p$ does not divide $a(a^2-1)$. Put $$ n_1=\frac{a^p-1}{a-1},\quad n_2=\frac{a^p+1}{a+1},\quad n=n_1n_2. $$ Then $n$ is a pseudoprime to base $a$. \end{theorem} In this paper we call such $n$ a {\it Cipolla pseudoprime}. In the above theorem, if we set $P=a+1$, $Q=a$, then $n$ is written as $n=U_{2p}/P$, where $U_{2p}$ is a term in the Lucas sequence with parameters $P$ and $Q$. See the next section for Lucas sequences. From this observation, the following question arises. For given integers $P, Q$, are there infinitely many Lucas pseudoprimes with parameters $P$ and $Q$ of the form $U_{2p}/P$? Here Lucas pseudoprimes will be defined in the next section. \par The purpose of the paper is to solve the above question affirmatively under a certain condition. As a corollary to our result, we derive the result of Lehmer \cite{Lehmer2}. We are also going to consider an analogous question for Lehmer sequences. \section{Cipolla-Lucas pseudoprimes} In this section we consider Lucas pseudoprimes of special type. \par Let $P, Q$ be integers such that $D:=P^2-4Q\ne 0$, and $\alpha , \beta$ the roots of the polynomial $z^2-Pz+Q$. For a nonnegative integer $n$, put $$ U_n=\frac{\alpha^n-\beta^n}{\alpha -\beta}, \quad V_n=\alpha^n+\beta^n. $$ For example, we have $U_0=1$, $U_1=1$, $U_2=P$, $V_0=2$, and $V_1=P$. One sees that $(U_n)_{n\geq 0}$ and $(V_n)_{n\geq 0}$ are integer sequences. We call the sequences $(U_n)_{n\geq 0}$, $(V_n)_{n\geq 0}$ the {\it Lucas sequences with parameters $P$ and $Q$}. \par We exhibit some results needed afterwards. One can consult Ribenboim \cite{Ribenboim1,Ribenboim2} for the basic results. \par \noindent (I) For a nonnegative integer $n$, $U_{2n}=U_nV_n$. \par \noindent (II) (a) If $P$ is odd and $Q$ is even, then $U_n$, $V_n$ ($n\geq 1$) are odd. \par (b) If $P$ and $Q$ are odd, then $U_n$, $V_n$ ($3\nmid n$) are odd. \par \noindent (III) (a) When $U_m\ne 1$, $U_m|U_n$ if and only if $m|n$. \par (b) When $V_m\ne 1$, $V_m|V_n$ if and only if $m|n$ and $n/m$ is odd. \par \noindent (IV) For any odd prime $p$, \begin{eqnarray} 2^{p-1}U_p&=&\sum_{k=0}^{(p-1)/2} \left(\begin{array}{c}p\\ 2k+1\end{array}\right) P^{p-(2k+1))}D^k, \\ 2^{p-1}V_p&=&\sum_{k=0}^{(p-1)/2} \left(\begin{array}{c}p\\ 2k\end{array}\right) P^{(p-2k)}D^k. \end{eqnarray} $$ U_p\equiv \left(\frac{D}{p}\right) \pmod p, \quad V_p\equiv P \pmod p . $$ \par We recall Lucas pseudoprimes. A composite number $n$ is a {\it Lucas pseudoprime with parameters $P$ and $Q$} if $$ U_{n-\left(\frac{D}{n}\right)} \equiv 0 \pmod n $$ holds. Here $\left(\frac{D}{n}\right)$ is the Jacobi symbol. \par Now let us define an analogue of Cipolla pseudoprimes for Lucas sequences. \begin{definition}\label{2}{\rm A composite number $n$ is called a {\it Cipolla-Lucas pseudoprime with parameters} $P$ and $Q$ if it is a Lucas pseudoprime with parameters $P$ and $Q$ and has the form $U_{2p}/P$ for a certain prime number $p$. } \end{definition} \par Our first result is as follows. \begin{theorem}\label{3} Let $P$ be an odd number, and $Q$ a nonzero integer such that ${\rm gcd}(P,Q)=1$. Assume that $D=P^2-4Q$ is square-free. Then there are infinitely many Cipolla-Lucas pseudoprimes with parameters $P$ and $Q$. \end{theorem} \begin{proof} Let $p$ be an odd prime such that $\text{gcd}(p,3PD)=1$ and $\varphi (D)|p-1$. Then we show that $U_{2p}/P$ is a Lucas pseudoprime. From now on we prove the theorem step by step. Put $m=U_{2p}/P$. \par First of all, we prove $m | U_{m-\left(\frac{D}{m}\right)}$. Since $p$ is odd, $U_p\equiv \left(\frac{D}{p}\right)\, (\bmod\, p), \, V_p\equiv P\, (\bmod\, p)$. So that $$ U_{2p}=U_pV_p\equiv P\left(\frac{D}{p}\right) \pmod p . $$ Since $P=U_2$, $U_2|U_{2p}$, and $\text{gcd}(p,P)=1$, we have $m\equiv \left(\frac{D}{p}\right) \, (\bmod\, p)$. We recall that $P$ is odd and $\text{gcd}(p,3)=1$. Hence $U_p$ and $V_p$ are odd. We see $2p| m-\left(\frac{D}{p}\right)$. From this, we have $U_{2p}| U_{m-\left(\frac{D}{p}\right)}$. Moreover we have $m|U_{m-\left(\frac{D}{p}\right)}$. We prove $\left(\frac{D}{p}\right) = \left(\frac{D}{m}\right)$. By (1) and (2), \begin{eqnarray*} 2^{p-1}U_p &\equiv & pP^{p-1}\pmod D , \\ 2^{p-1}V_p &\equiv & P^p\pmod D . \end{eqnarray*} By $\varphi (D)|p-1$, we have $U_p\equiv p\, (\bmod\, D),\, V_p\equiv P\, (\bmod\, D)$. Hence $U_{2p}\equiv pP\, (\bmod\, D)$. By $\text{gcd}(P,D)=1$, it follows that $m=U_{2p}/P\equiv p\, (\bmod\, D)$. Observe that $D\equiv 1\, (\bmod\, 4)$ because $P$ is odd. Thus we have $\left(\frac{D}{p}\right) = \left(\frac{D}{m}\right)$, which implies $m|U_{m-\left(\frac{D}{m}\right)}$. \par We next show that $m$ is a composite number. Since $p$ is odd and $P=U_2=V_1$, one has $P\nmid U_p$ and $P|V_p$. Now assume that there exists an odd prime $p$ satisfying $V_p=\pm P$. Then one has $V_1|V_p$ and $V_p|V_1$. This implies $p=1$, which is absurd. Therefore $m$ is a composite number. \par Finally, we prove the infinitude of $U_{2p}/P$. By Dirichlet's theorem on primes in arithmetic progression, there are infinitely many primes $p$ such that $\varphi (D)|p-1$. The number of primes $p$ with $\text{gcd}(p,3PD)> 1$ among them is finite. This proves the claim. \end{proof} \vspace{2mm} As a corollary to the last theorem, we can derive a known result. We call the Lucas sequence with parameters $1$ and $-1$ the {\it Fibonacci sequence}. We write $(F_n)_{n\geq 0}$ for it. A composite number $n$ is called a {\it Fibonacci pseudoprime} if $$ F_{n-\left(\frac{D}{n}\right)}\equiv 0\pmod n $$ is valid. Using the last theorem, we have \begin{corollary}[Lehmer \cite{Lehmer2}]\label{4} There are infinitely many primes $p$ such that $F_{2p}$ is a Fibonacci pseudoprime. \end{corollary} \begin{proof} Since $P=1$ and $Q=-1$, $U_{2p}/P$ becomes $F_{2p}$. In this case one has $D=5$. Hence for any prime $p>5$ with $p\equiv 1\, (\bmod\, 4)$, the two conditions $\text{gcd}(p, 3PD)=1$ and $\varphi (D)|p-1$ hold. This yields the result. \end{proof} \section{Cipolla-Lehmer pseudoprimes} In this section we consider Lehmer pseudoprimes. First, we review Lehmer sequences. \par Let $\alpha , \beta$ be distinct roots of the polynomial $f(z)=z^2-\sqrt{L}z+M$, where $L>0$ and $M$ are rational integers, and $K:=L-4M$ is the discriminant of $f(z)$. For a nonnegative integer $n$, put \begin{eqnarray*} D_n&=&\left\{ \begin{array}{cc} (\alpha^n-\beta^n)/(\alpha -\beta) & \text{if\, $n$\, is\, odd} \\ (\alpha^n-\beta^n)/(\alpha^2 -\beta^2) & \text{if\, $n$\, is\, even}, \end{array} \right. \\ E_n&=&\left\{ \begin{array}{cc} (\alpha^n+\beta^n)/(\alpha +\beta) & \text{if\, $n$\, is\, odd} \\ \alpha^n+\beta^n & \text{if\, $n$\, is\, even}. \end{array} \right. \end{eqnarray*} For example, we have $D_0=0$, $D_1=D_2=1$, $E_0=2$, $E_1=1$, and $E_2=L-2M$. One sees that $(D_n)_{n\geq 0}$ and $(E_n)_{n\geq 0}$ are integer sequences. We call the sequences $(D_n)_{n\geq 0}$ and $(E_n)_{n\geq 0}$ the {\it the Lehmer sequences with parameters $L$ and $M$}. It should be noticed that we modify the original definition of the Lehmer sequences in order to make them integer sequences. \par We exhibit some results needed afterwards. One can consult Lehmer \cite{Lehmer1} for the basic results. \par \noindent (I) For a prime $p$, $D_{2p}=D_pE_p$. \par \noindent (II) $D_n$ is even in the following cases only \par (a) $L=4k$, $M=2l+1$, $n=2h$, \par (b) $L=4k+2$, $M=2l+1$, $n=4h$, \par (c) $L=4k\pm 1$, $M=2l+1$, $n=3h$. \par \noindent (III) $E_n$ is even in the following cases only \par (a) $L=4k$, $M=2l+1$, \par (b) $L=4k+2$, $M=2l+1$, $n=2h$, \par (c) $L=4k\pm 1$, $M=2l+1$, $n=3h$. \par \noindent (IV) If $m|n$, then $D_m|D_n$. \par \noindent (V) For any odd prime $p$, \begin{eqnarray} 2^{p-1}D_p&=&\sum_{k=0}^{(p-1)/2} \left(\begin{array}{c}p\\ 2k+1\end{array}\right) L^{(p-2k-1)/2}K^k, \\ 2^{p-1}E_p&=&\sum_{k=0}^{(p-1)/2} \left(\begin{array}{c}p\\ 2k\end{array}\right) L^{(p-2k)/2}K^k. \end{eqnarray} $$ D_p\equiv \left(\frac{K}{p}\right)\pmod p , \quad E_p\equiv \left(\frac{L}{p}\right)\pmod p . $$ \par Next, we review Lehmer pseudoprimes. A composite number $n$ is called a {\it Lehmer pseudoprime with parameters $L$ and $M$} if $$ D_{n-\left(\frac{KL}{n}\right)} \equiv 0\pmod n $$ holds. Here $\left(\frac{KL}{n}\right)$ denotes the Jacobi symbol. \par Any Cipolla pseudoprime is written as $D_{2p}$ for some prime $p$. Hence we define Lehmer pseudoprimes related to Cipolla pseudoprimes as follows. \begin{definition}\label{5}{\rm A composite number $n$ is called a {\it Cipolla-Lehmer pseudoprime with parameters $L$ and $M$} if it is a Lehmer pseudoprime with parameters $L$ and $M$ and has the form $D_{2p}$ for a certain prime $p$} \end{definition} \par Our second result is as follows. \begin{theorem}\label{6} Let $L$ be a square-free odd number and $M$ an integer such that ${\rm gcd}(L,M)=1$. Assume that $K=L-4M$ is square-free. Then there are infinitely many Cipolla-Lehmer pseudoprimes with parameters $L$ and $M$. \end{theorem} \begin{proof} The proof is similar to that of Theorem~\ref{3}. Let $p$ be an odd prime such that $\text{gcd}(p, KL)=1$ and $\varphi (KL)| p-1$. Then we prove that $D_{2p}$ is a Lehmer pseudoprime. Put $m=D_{2p}$. \par We first show $m| D_{m-\left(\frac{KL}{m}\right)}$. Since $p$ is odd, $D_{p}\equiv\left(\frac{K}{p}\right)\, (\bmod\, p)$, $E_{p}\equiv\left(\frac{L}{p}\right)\, (\bmod\, p)$. Hence $$ m=D_{2p}=D_pE_p\equiv \left(\frac{KL}{p}\right)\pmod p . $$ That is to say, $p|m-\left(\frac{KL}{p}\right)$. Since $L$ is odd, $D_p$ and $E_p$ are odd. Hence $m$ is odd. We find that $m-\left(\frac{KL}{p}\right)$ is even. Thus $2p|m-\left(\frac{KL}{p}\right)$. Using this, we have $D_{2p}|D_{m-\left(\frac{KL}{p}\right)}$, which shows $m|D_{m-\left(\frac{KL}{p}\right)}$. We must prove $\left(\frac{KL}{p}\right) = \left(\frac{KL}{m}\right)$. Since $K$ is odd, by (3) and (4), \begin{eqnarray*} 2^{p-1}D_p&\equiv & pL^{\frac{p-1}{2}}+K^{\frac{p-1}{2}} \pmod {KL} ,\\ 2^{p-1}E_p &\equiv & L^{\frac{p-1}{2}}+pK^{\frac{p-1}{2}} \pmod {KL} . \end{eqnarray*} Since $\varphi (KL)|p-1$ and $2\nmid KL$ hold, $2^{p-1}\equiv 1\, (\bmod\, KL)$. Hence we have $$ m=D_pE_p\equiv p\left(K^{p-1} +L^{p-1}\right)\pmod {KL} . $$ It should be noted that $K^{p-1}+L^{p-1} \equiv 1\, (\bmod\, KL)$. Indeed, because of $\text{gcd}(K,L)=1$, the condition $\varphi (K)\varphi (L)|p-1$ implies $L^{p-1}\equiv 1\, (\bmod\, K)$ and $K^{p-1}\equiv 1\, (\bmod\, L)$. For any prime divisor $l$ of $K$, $l|K^{p-1}+L^{p-1}-1$. Hence we have $K^{p-1}+L^{p-1}-1\equiv 0\, (\bmod\, K)$. In the same way, we have $K^{p-1}+L^{p-1}-1\equiv 0\, (\bmod\, L)$. Therefore our claim is proven. Using this observation, we obtain $m\equiv p\, (\bmod\, KL)$. By the way, we see $KL=L^2-4ML\equiv L^2\equiv 1\, (\bmod\, 4)$. Thus we conclude that $\left(\frac{KL}{p}\right) =\left(\frac{KL}{m}\right)$. We get $m|D_{m-\left(\frac{KL}{m}\right)}$. \par Clearly $m=D_pE_p$ is a composite number. \par Finally we show the infinitude of $D_{2p}$. By Dirichlet's theorem on primes in arithmetic progression, there are infinitely many primes $p$ such that $\varphi (KL)|p-1$. The number of primes $p$ with $\text{gcd}(p,KL)> 1$ among them is finite. This proves the claim. \end{proof} \begin{thebibliography}{99} \bibitem{Cipolla}M. Cipolla, \newblock Sui numeri composti $P$, che verificanola congruenza di Fermat $a^{P-1}\equiv 1\ (\bmod\, P)$. \newblock {\em Annali di Matematica} {\bf 9} (1904), 139--160. \bibitem{Koblitz}N. Koblitz, \newblock {\em A Course in Number Theory and Cryptography.} \newblock Springer-Verlag, 1994. \bibitem{Lehmer1}D. H. Lehmer, \newblock An extended theory of Lucas' functions. \newblock {\em Annals of Math.} {\bf 31} (1930), 419--448. \bibitem{Lehmer2}E. Lehmer, \newblock On the infinitude of Fibonacci pseudo-primes. \newblock {\em Fibonacci Quart.} {\bf 2} (1964), 229--230. \bibitem{Ribenboim1}P. Ribenboim, \newblock {\em The Book of Prime Number Records.} \newblock Springer-Verlag, 1989. \bibitem{Ribenboim2}P. Ribenboim, \newblock {\em My Numbers, My Friends $-$ Popular Lectures on Number Theory.} \newblock Springer-Verlag, 2003. \bibitem{Rotkiewicz1}A. Rotkiewicz, \newblock Lucas pseudoprimes. \newblock {\em Functiones et Approximatio} {\bf XXVIII} (2000), 97--104. \bibitem{Rotkiewicz2}A. Rotkiewicz, \newblock Arithmetic progressions formed by pseudoprimes. \newblock {\em Acta Mathematica et Informatica Universitatis Ostraviensis} {\bf 8} (2000) 61--74. \bibitem{Serre}J.-P. Serre, \newblock {\em Cours d'arithm\'etique.} \newblock Presses Universitaires de France, 1970. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 11A51; Secondary 11B39.\\ \noindent {\it Keywords:} pseudoprime, Lucas sequence, Lucas pseudoprime, Lehmer sequence, Lehmer pseudoprime. \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received July 17 2007; revised version received August 1 2007. Published in {\it Journal of Integer Sequences}, August 14 2007. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}