\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}