\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{amsfonts} \usepackage{latexsym} \usepackage{epsf} \usepackage{amsthm} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \def\QQ{\mathbb Q} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \DeclareMathOperator{\lcm}{lcm} \def\N{\mathbb{N}} \def\R{\mathbb{R}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf{On a Compositeness Test for $(2^p+1)/3$}} \vskip 1cm \large Pedro Berrizbeitia \\ Departmento de Matem\'aticas Pura y Aplicada\\ Universidad Sim\'on Bol\'\i var\\ Caracas, Venezuela\\ \href{mailto:pedrob@usb.ve}{\tt pedrob@usb.ve}\\ \ \\ Florian Luca\\ Instituto de Matem{\'a}ticas\\ Universidad Nacional Autonoma de M{\'e}xico \\ C.P. 58089, Morelia, Michoac{\'a}n\\ M{\'e}xico\\ \href{mailto:fluca@matmor.unam.mx}{\tt fluca@matmor.unam.mx}\\ \ \\ Ray Melham\\ Department of Mathematical Sciences\\ University of Technology, Sydney\\ PO Box 123 \\ Broadway, NSW 2007 \\ Australia\\ \href{mailto: ray.melham@uts.edu.au}{\tt ray.melham@uts.edu.au}\\ \end{center} \vskip .2 in \begin{abstract} In this note, we give a necessary condition for the primality of $(2^p+1)/3$. \end{abstract} \renewcommand{\theequation}{\arabic{equation}} \renewcommand{\theequation}{\arabic{equation}} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{claim}[theorem]{Claim} \newtheorem{cor}[theorem]{Corollary} \newtheorem{prop}[theorem]{Proposition} \newtheorem{definition}{Definition} \newtheorem{thm}{Theorem} \newtheorem{exam}{Example} \newtheorem{example}[exam]{Example} \newtheorem{lem}[thm]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{prob}{Problem} \newtheorem{problem}[prob]{Problem} \newtheorem{ques}{Question} \newtheorem{question}[ques]{Question} \newtheorem{conj}[theorem]{Conjecture} \def\Z{{\mathbb Z}} \def\K{{\mathbb K}} \def\F{{\mathbb F}} \section{Introduction} Let $p$ be an odd prime and $M_{p}:=2^{p}-1$. For $n\geq0$ define the sequence $\left\{S_n\right\}_{n\ge 0}$ by \begin{eqnarray*} S_{0}&=&4,\\ S_{k+1}&=&S_{k}^{2}-2, \qquad k\geq0. \end{eqnarray*} The celebrated Lucas-Lehmer test states: \begin{theorem}\label{thm1} $M_{p}$ is prime if and only if $S_{p-2}\equiv 0\pmod {M_p}$. \end{theorem} The numbers $M_{p}$ have interested experts and non-experts throughout history. See \cite{Wi} for an interesting mathematical and historical account. These numbers have been a popular focus among those searching for large primes because of their unique set of convenient properties for primality testing, the most important of these being the Lucas-Lehmer test, given in Theorem \ref{thm1}. Indeed, via Lucas-Lehmer test, the determination of the primality of $M_p$ is achieved through the calculation of $p-2$ ($<\log M_p$) squares modulo $M_p$. Furthermore, the reduction of a $2p$-bit integer modulo $M_p$ is very fast compared to the reduction modulo any other number of a similar size. Observe that $M_p= \phi_p(2)$, where $\phi_p(X)$ is the $p$-th cyclotomic polynomial. In this paper, we look at primes of the form $$ N_p:=\phi_p(-2)=\frac{2^p+1}{3}. $$ For $p$ a prime, the family of numbers $\{N_p\}_{p\ge 3}$ shares some of the properties that make the numbers $\{M_p\}_{p\ge 3}$ interesting to searchers of large primes. For instance, if $N_p$ is prime, then $p$ must be a prime. Additionaly, divisors of $N_p$ are congruent to $1$ modulo $2p$, an observation that helps in the search for small prime divisors of $N_p$. Furthermore, Melham proved the following theorem (see Theorem 7 in \cite{Ray1}), to which we will refer as Melham's probable prime test for $N_p$. \begin{theorem} \label{thm:MPPT} Let $p$ be an odd prime. Define the sequence $\left\{S_n\right\}_{n\geq 0}$ by \begin{eqnarray*} S_{0}&=& 6,\\ S_{k+1}&=& S_{k}^{2}-2, \qquad k\geq0. \end{eqnarray*} If $N_p$ is prime then $S_{p-1}\equiv -34\pmod {N_p}$. \end{theorem} Similar congruences involving Fibonacci numbers and more general Lucas sequences instead of only Mersenne numbers appear in \cite{An} and \cite{Beli}. It is easy to see that the reduction of a $2p$-bit number modulo $N_p$ is also very fast. However, it is not known whether the numbers $\{N_p\}_{p\ge 3}$ have a very important property enjoyed by the numbers $\{M_p\}_{p\ge 3}$. Specifically, it is not known if $S_{p-1}\equiv -34\pmod {N_p}$ implies that $N_p$ is prime. The numbers $\{N_p\}_{p\ge 3}$ were studied by Bateman, Selfridge, and Wagstaff, Jr. \cite{bat} who proposed the following conjecture. \begin{conj} If two of the following statements about an odd positive integer $p$ are true, then the third one is also true. \begin{itemize} \item $p=2^{k}\pm1$ or $p=4^{k}\pm3$; \item $M_{p}$ is prime; \item $N_{p}$ is prime. \end{itemize} \end{conj} Currently, there are forty known primes/probable primes $N_{p}$, sometimes called Wagstaff primes/PRP. See, for example, \cite{wiki}. Probable primes $N_{p}$ can be discovered via any of the known pseudoprime tests. Examples of such tests are the strong pseudoprime test (or the Miller-Rabin test \cite{Ra}), and the Grantham test \cite{Gra}. They can also be discovered with the use of Melham's probable prime test, given in Theorem \ref{thm:MPPT} above. This test has the computational advantadge of involving the computation of only $p-1$ modular squares, the subtraction of $2$ in each step being neglected. Melham's probable prime test for $N_p$ can be derived by the application of a Frobenius test to $1+\sqrt 2$ in the finite field $\K: = \Z[\sqrt{2}]/N_p$. The application of the Frobenius test is equivalent to the determination of the quadratic character of $1 + \sqrt{2}$ in $\K$. Similarly, we will see that, by the application of a Frobenius test to $2+\sqrt{2}$, one can obtain the following weaker variant of Melham's test: If $N_p$ is prime, then the sequence given by \begin{eqnarray*} R_{0}&=& 4,\\ R_{k+1} &=& R_{k}^2-2^{2^k+1}, \qquad k\geq0, \end{eqnarray*} satisfies $R_{p-1}^2 \equiv 64 \pmod {N_p}$ (see Lemma \ref{lem:2} below). Curiously, we noticed experimentally that whenever $N_p$ is prime, then $R_{p-1}\equiv 8 \pmod {N_p}$ holds. The object of this paper is to show that this is indeed the case. Our proof hinges on the determination of the biquadratic character of $2+\sqrt{2}$ in $\K$, a problem that we consider to be interesting in its own right. \section{The Main Result} \begin{theorem} \label{theorem:1} If $p> 3$ is prime, and $N_p$ is prime, then $R_{p-1}\equiv 8\pmod {N_p}$. \end{theorem} Let $\alpha:=2+{\sqrt{2}}$ and $\beta:=2-{\sqrt{2}}$. It is easy to see, by induction on $n$, that the formula \begin{equation} \label{eq:Rn} R_n=\alpha^{2^n}+\beta^{2^n}\qquad {\text{\rm holds~for~all}}~n\ge 0. \end{equation} Since $p> 3$, it follows easily that $N_p\equiv 3\pmod 8$. In particular, \begin{equation} \label{eq:Jacobi} \left(\frac{-1}{N_p}\right)=\left(\frac{2}{N_p}\right)=-1, \end{equation} where, as usual, for integers $a$, and $q\ge 3$ odd, we write ${\displaystyle{\left(\frac{a}{q}\right)}}$ for the Jacobi symbol of $a$ with respect to $q$. \medskip We start by giving a short proof of a somewhat weaker congruence using nothing else but the properties of the Frobenius automorphism. \begin{lemma}\label{lem:2} Let $p> 3$ be prime. If $N_p$ is prime, then $R_{p-1}^2\equiv 64\pmod {N_p}.$ \end{lemma} \begin{proof} Assume that $q:=N_p$ is prime. Again let $\K:=\F_{q}[{\sqrt{2}}]$. By equation \eqref{eq:Jacobi}, it follows that $\K$ is a finite field with $q^2$ elements. Since $\alpha\not\in \F_q$, we have that $\alpha^q=\beta$ in $\K$. Then $\alpha^{3q}=\beta^3$. Since $3q=2^p+1$, it follows that $$ \alpha^{2^p}=\beta^3\alpha^{-1}. $$ Conjugating the above relation, we get $$ R_p=\alpha^{2^p}+\beta^{2^p}=\beta^3\alpha^{-1}+\alpha^3\beta^{-1}=\frac{\alpha^4+\beta^4}{\alpha\beta}=68, $$ where we have used the relations $$ \alpha^4=68+48{\sqrt{2}},\qquad \beta^4=68-48{\sqrt{2}},\qquad \alpha\beta=2. $$ However, again by formula \eqref{eq:Jacobi}, we have $$ 2^{(q-1)/2}=-1~~{\text{\rm in}}~~\F_q. $$ Since $(q-1)/2=(2^{p-1}-1)/3$, we conclude that \begin{equation} \label{eq:pp} 2^{2^{p-1}-1}=-1. \end{equation} Thus, $2^{2^{p-1}+1}=-4$. The desired relation now follows because $$ R_{p-1}^2=R_{p}+2^{2^{p}+1}=68-4=64, $$ which is what we wanted. \end{proof} Let us now go to the proof of Theorem \ref{theorem:1}. We shall assume that $p> 3$, since for $p=3$ the congruence can be verified directly. We keep the previous notations. Let $i$ be a fixed square-root of $-1$ in $\K$. Put $$ \gamma:=1+i+{\sqrt{2}}. $$ Let $$ \sigma:=1+i-{\sqrt{2}}\qquad {\text{\rm and}}\qquad \tau:=1-i+{\sqrt{2}}. $$ Note that none of the elements $\gamma,~\sigma,~\tau$ is in $\F_q$. Indeed, assume say, that $\tau\in \F_q$. Then by writing $-i+{\sqrt{2}}=a$ with some $a\in \F_q$, rearranging the above relation and squaring it, we get $$ -1=(-i)^2=(a-{\sqrt{2}})^2=a^2-2a{\sqrt{2}}+2, $$ so that $a{\sqrt{2}}\in \F_q$, which is possible only if $a=0$. However, with $a=0$ the above relation becomes $-1=2$, which is false because $q=N_p>3$. Observe now that $$ \sigma\tau=1-(i-{\sqrt{2}})^2=2i{\sqrt{2}}=2{\sqrt{-2}}\in \F_q, $$ where the last relation follows from the fact that $-2$ is a quadratic residue modulo $q$. Thus, $(\sigma\tau)^{q-1}=1$. Since $(q^2-1)/4=(q-1)((q+1)/4)$ is a multiple of $q-1$, we see that $(\sigma\tau)^{(q^2-1)/4}=1$, which can be rewritten as \begin{equation} \label{eq:imp} (\gamma\tau)^{(q^2-1)/4}=(\gamma\sigma)^{(q^2-1)/4}\left({\tau^2}\right)^{(q^2-1)/4}. \end{equation} Now, \begin{equation} \label{eq:2alpha} \gamma \sigma=(1+i)^2-2=2(i-1),\qquad {\text{\rm and}}\qquad \gamma\tau=(1+{\sqrt{2}})^2-i^2=2\alpha. \end{equation} Observe that $2(i-1)=-2{\sqrt{2}} \omega$, where $\omega=(1-i)/{\sqrt{2}}$ is a root of unity of order $8$. Since $p\ge 5$, it follows that $q\equiv 3^{-1}\equiv 11\pmod {32}$, which implies easily that $(q^2-1)/4\equiv -2\pmod 8$. Thus, the left side of formula \eqref{eq:imp} is \begin{equation} \label{eq:1} (\gamma\sigma)^{(q^2-1)/4}=(-2{\sqrt{2}})^{(q^2-1)/4} \omega^{(q^2-1)/4}= (-1)^{(q^2-1)/4} 2^{3(q^2-1)/8} \omega^{-2}=-i. \end{equation} Next, observe that $$ (\tau^2)^{(q^2-1)/4}=\left(\tau^{q+1}\right)^{(q-1)/2}. $$ By Frobenius, we have that $\tau^{q+1}=\tau^q\tau=\sigma\tau=2i{\sqrt{2}}. $ Thus, \begin{equation} \label{eq:2} (\tau^2)^{(q^2-1)/4}=(2i{\sqrt{2}})^{(q-1)/2}=i^{(q-1)/2} 2^{(q-1)/2} ({\sqrt{2}})^{(q-1)/2}=-i({\sqrt{2}})^{(q-1)/2}, \end{equation} where we have used the fact that $(q-1)/2\equiv 1\pmod 4$, which follows easily from the fact that $q\equiv 11\pmod {32}$. Inserting \eqref{eq:1} and \eqref{eq:2} into \eqref{eq:imp}, and using also \eqref{eq:2alpha}, we obtain $$ (2\alpha)^{(q^2-1)/4} = (-i)(-i)({\sqrt{2}})^{(q-1)/2} = - ({\sqrt{2}})^{(q-1)/2}. $$ Using now $2^{(q^2-1)/4}=(2^{q-1})^{(q+1)/4}=1$, and $\alpha^{q-1}=\alpha^q\alpha^{-1}=\beta/\alpha$, we deduce that $$ \left(\frac{\beta}{\alpha}\right)^{(q+1)/4}=\alpha^{(q^2-1)/4}=(2\alpha)^{(q^2-1)/4}=-({\sqrt{2}})^{(q-1)/2}. $$ Now, $(q+1)/4=(2^p+4)/12=(2^{p-2}+1)/3$. Thus, $$ \left(\frac{\beta}{\alpha}\right)^{2^{p-2}}=-({\sqrt{2}})^{3(q-1)/2}\left(\frac{\alpha}{\beta}\right). $$ Applying the Frobenius automorphism, and summing the resulting relations, we arrive at $$ \left(\frac{\beta}{\alpha}\right)^{2^{p-2}}+\left(\frac{\alpha}{\beta}\right)^{2^{p-2}}= -({\sqrt{2}})^{3(q-1)/2}\left(\frac{\alpha}{\beta}-\frac{\beta}{\alpha}\right). $$ In the line immediately above, the left side is $R_{p-1}/(\alpha\beta)^{2^{p-2}}=R_{p-1}/2^{2^{p-2}}.$ The right side is $$ -({\sqrt{2}})^{3(q-1)/2}\left(\frac{\alpha^2-\beta^2}{\alpha\beta}\right)=-({\sqrt{2}})^{3(q-1)/2} 4{\sqrt{2}}= -2^{(3q+7)/4}. $$ Since $(3q+7)/4=2^{p-2}+2$, we obtain $$ \frac{R_{p-1}}{2^{2^{p-2}}}=-2^{2^{p-2}+2}, $$ which finally leads to $R_{p-1}=-2^{2^{p-1}+2}$. Using \eqref{eq:pp}, we obtain the desired result. \medskip \section{Acknowledgements} We thank the anonymous referees and Professor Jeffrey Shallit for useful remarks and for suggesting some references. This work was done while the first two authors attended the {\it Terceras Jornadas de Teoria de N\'umeros} in Salamanca, Spain in July of 2009. They thank the organizers of this event for the opportunity to attend this meeting and for financial support and to Javier Cilleruelo for enlightening conversations. We also thank the Astronaut who inspired the current approach to the problem. P.~B. was also supported in part by the Decanato de Investigaciones from the Universidad Sim\'on Bol\'{\i}var, and F.~L. was supported in part by Grants SEP-CONACyT 79685 and PAPIIT 100508. \begin{thebibliography}{99} \bibitem{An} G.~Andrews, Some formulae for the Fibonacci sequence with generalizations, {\it Fibonacci Quart.\/} {\bf 7} (1969), 113--130. \bibitem{bat} P. T. Bateman, J. L. Selfridge, and S. S. Wagstaff, The new Mersenne conjecture, {\it Amer. Math. Monthly}, \textbf{96} (1989), 125--128. \bibitem{Beli} C.~N.~Beli, Two conjectures by Zhi-Hong Sun, {\it Acta Arith.\/} {\bf 137} (2009), 99--131. \bibitem{Gra} J.~Grantham, A probable prime test with high confidence {\it J. Number Theory\/} {\bf 72} (1998), 32--47. \bibitem{Ray1} R.~S.~Melham, Probable prime tests for generalized Mersenne numbers, {\it Bol. Soc. Mat. Mexicana\/} {\bf 14} (2008), 7--14. \bibitem{Ra} M.~O.~Rabin, Probabilistic algorithm for testing primality, {\it J. Number Theory\/} {\bf12} (1980), 128--138. \bibitem{Wi} H.~Williams, {\it Edouard Lucas and Primality Testing\/}, Canadian Math. Soc. Monographs {\bf 22}, Wiley, New York, 1998. \bibitem {wiki} Wagstaff prime, Wikipedia entry, \href{http://en.wikipedia.org/wiki/Wagstaff_prime}{\tt http://en.wikipedia.org/wiki/Wagstaff\_prime} . \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 11Y11; Secondary 11A41, 11A51. \noindent \emph{Keywords: } primality, Wagstaff primes. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A000979}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received November 16 2009; revised version received January 14 2010. Published in {\it Journal of Integer Sequences}, January 18 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}