<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
All Elite Primes Up to 250 Billion}
\vskip 1cm
\large
Alain Chaumont\\
Laboratoire de Mod\'elisation et Simulations Mol\'eculaires ``MSM'' \\
Universit\'e Louis Pasteur \\
4, rue B. Pascal \\
67000 Strasbourg \\
France\\ 
\href{mailto:chaumont@chimie.u-strasbg.fr}{\tt chaumont@chimie.u-strasbg.fr}\\
\ \\
Tom M\"uller\\
Institut f\"ur Cusanus-Forschung \\
Universit\"at Trier\\
Domfreihof 3 \\
54290 Trier\\ 
Germany \\
\href{mailto:muel4503@uni-trier.de}{\tt muel4503@uni-trier.de}
\end{center}

\vskip .2 in

\begin{abstract}
A prime number $p$ is called {\it elite} if only finitely many Fermat numbers
$2^{2^n}+1$ are quadratic residues of $p$. Previously only the interval up
to $10^9$ was systematically searched for elite primes and 16 such
primes were found. We extended this research up to $2.5\cdot 10^{11}$
and found five further elites, among which 1\,151\,139\,841 is the
smallest and 171\,727\,482\,881 the largest.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 


%\usepackage{amsmath}
%\usepackage{amsfonts}
%\usepackage{amssymb}

%\begin{document}


\section{Introduction}

Let $\{F_n\}$ with $F_n:=2^{2^n}+1$ denote the sequence of Fermat numbers.
Further details on these numbers, some of their properties and open
problems can be found, e.g., in the work of Hardy and
Wright~\cite{hardy}, in section A3 of Guy's problem book~\cite{guy} or
in the \textit{17 lectures} on this topic by K\v r\'i\v zek, Luca and
Somer~\cite{kri2}.

We call a prime number $p$ {\it elite}, if there is an integer index $m$ for
which all $F_{n}$ with $n&gt;m$ are quadratic non-residues of $p$, i.e.,
there is no solution to the congurence $x^2 \equiv F_n$ (mod
$p$) for $n&gt;m$. Alexander Aigner~\cite{aigner}, who first defined and
studied elite primes, discovered 14 such numbers with values less than
35 million. Two further primes less than $10^9$ were found by the second
author~\cite{muller}. All these primes are summarized in Table
\ref{tab1}.

\begin{table}[H]

\begin{center}\begin{tabular}{|c|c|}

\hline

elite primes 	&amp; discovered\\ \hline

3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041,&amp;\\

163841, 544001, 604801, 6684673, 14172161 &amp; Aigner (1986)\\ \hline

159318017, 446960641 &amp; M\"uller (2005)\\

\hline

\end{tabular}\caption{All elite primes $&lt; 10^9$}\label{tab1}\end{center}

\end{table}

A further important result was given by K\v r\'i\v zek, Luca and
Somer~\cite{kri} with a theorem assuring that the series $S$ of the
reciprocals of all  elite primes is convergent. They proved their claim
by showing that the number $N(x)$ of elite primes less than or equal to
$x$ is asymptotically bounded by the same functions as prime twins are,
i.e.,
\begin{eqnarray}\label{ass}
N(x)=O\left(\frac{x}{(\log x)^2}\right).
\end{eqnarray}

Further computations of larger elite primes~\cite{muller} suggested
moreover that the asymptotic (\ref{ass}) is rather rough and could
perhaps be lowered to
\begin{eqnarray}\label{as1}
N(x)=O\left( (\log x)^c \right),
\end{eqnarray}
with an option for $c=1$. This would mean that all larger interval of the form $\left[10^n,10^{n+1}\right]$ should contain 
a more or less constant number of elite primes.

The purpose of the project presented in this paper was to find all
elite primes up to $2.5\cdot 10^{11}$. These results seem to confirm
conjecture (\ref{as1}).



\section{Preliminaries}

From the well-known relation for Fermat numbers
\begin{eqnarray}\label{one}
F_{n+1}=(F_n-1)^2+1
\end{eqnarray}
it is obvious that for any prime number $p$,
the residues $F_n \bmod p$ are ultimately periodic.
Aigner~\cite{aigner} showed that for any prime number written in the
form $p=2^rh+1$ with $r\in\mathbb{N}$ and $h\geq 1$ odd, this period
begins at the latest with the term $F_r$. We call $L$ the
\textit{length of the Fermat period}, if $L$ is the smallest natural
number fulfilling the congruence $F_{r+L}\equiv F_r$ (mod $p$). The terms
$F_{r+\nu}\bmod p$ with $\nu=0,\ldots,L-1$ are called \textit{Fermat
remainders} of $p$.

Therefore, a prime number $p$ is elite if and only if all $L$ Fermat
remainders are quadratic non-residues modulo $p$. It is moreover known
that for all $p&gt;10$ it is a necessary condition for eliteness that $L$
is an even number smaller than $\frac{p-1}{4}$
(compare~\cite{aigner}).

But it seems that the Fermat periods of elite primes are very often of
particularly small length $L$. Actually, for all examples known to
date~\cite{muller}, we have $L\leq 12$ with a vast majority of cases
where $L=4$.



\section{The method}

First, we constructed all prime numbers in the range up to 250 billion
with the help of a variant of the well-known sieve method of
Erathostenes. It is proved in \cite{aigner} that prime numbers of the
form $p=120k+a$ with $k\in\mathbb{N}$ and
$a\in\{11,13,19,23,31,47,59,61,71,79,91,109,119\}$ cannot be elite, so
that a simple preliminary congruential test combined with some
elementary results on quadratic residues already allowed one to
eliminate a large number of candidates. All the remaining prime numbers
were tested one by one using an algorithm based on the following
necessary and sufficient condition:

\newtheorem{theo1}{Theorem}[section]

\begin{theo1}\label{theo1a}
Let $p=2^{\,r}h+1$ be a prime number with $h$ odd. Then $p$ is elite if
and only if every Fermat remainder has a multiplicative order modulo
$p$ being a multiple of $2^{\,r}$.
\end{theo1}

So, if $f$ denotes a given Fermat remainder of a prime $p=2^{\,r}h+1$, the algorithm checked whether the congruence
\begin{eqnarray}\label{hh}
f^{\, 2^{k}h} \equiv 1 \ \ ({\rm mod}\ p) 
\end{eqnarray}
is solvable only for $k=r$. If this is fulfilled, equation (\ref{hh})
is solved for the next Fermat remainder of $p$ and so on, until either
an entire Fermat period is successfully checked and hence $p$ is elite,
or a Fermat remainder $f$ is found with $k&lt;r$ in (\ref{hh}) leading to
a negative answer regarding the eliteness of $p$ (compare
\cite{muller}).

As in all known cases elite primes have Fermat periods of rather small
length and moreover almost all non-elite primes in our research
presented rather quickly a Fermat remainder contradicting the
sufficient condition of theorem \ref{theo1a}, the computational effort
needed for testing a given $p$ turned out to be on average equivalent
to five Fermat-tests.



\section{The results}

In the interval $[10^9, 2.5\cdot 10^{11}]$ we found five elite primes.
Two primes were found between $10^9$ and $10^{10}$, while the set of
elite primes contained in the interval $[10^{10},3\cdot 10^{10}]$ is
empty. Only one further elite was discovered smaller than 100 billion.
Two supplementary primes turned up between $10^{11}$ and $2\cdot
10^{11}$. The final subinterval again turned out to be ``elite-free".
These elite primes are listed in Table \ref{table1} together with the
respective length $L$ of their Fermat period.

So, there are 21 elite prime numbers less than 250 billion and in total 45 such primes known to date.

\begin{table}[H]

\begin{center}\begin{tabular}{|r|c|}

\hline

$p$ 			&amp;  $L$\\ \hline

1\,151\,139\,841	&amp; 4	\\

3\,208\,642\,561	&amp; 4	\\

38\,126\,223\,361	&amp; 4	\\

108\,905\,103\,361	&amp; 4	\\

171\,727\,482\,881	&amp; 8	\\

\hline

\end{tabular}\caption{All elite primes between $10^9$ and 250 billion}\label{table1}\end{center}

\end{table}

The results of this section as well as the known numbers presented in
the introduction are summarized in Sloane's OEIS \seqnum{A102742}.

The several computations were run on a AMD Sempron 2600 XP+ and a
Pentium-III-processed PC. A total CPU-time of about 1680 hours was
needed to complete this project.



\section{Interpretations and conjectures}

It was conjectured that there are infinitely many elite primes. If this
is so, it is certainly interesting to know more about their
distribution among natural numbers. Table \ref{table2} gives a
comparison of $N(x)$ and $\log x$ for some $x$ in the interval
$\left[10,2.5\cdot 10^{11}\right]$ suggesting that the growth of both
functions is perhaps asymptotically the same.

\begin{table}[H]

\begin{center}\begin{tabular}{|c|c|c|}

\hline

$x$ 			&amp;  $N(x)$	&amp; $\log x$\\ \hline

$10$			&amp; 3		&amp;	2.3\\

$10^2$			&amp; 4		&amp;	4.6\\

$10^5$			&amp; 9		&amp;	11.5\\

$10^6$			&amp; 12		&amp;	13.8\\

$10^9$			&amp; 16		&amp;	20.7\\

$2.5\cdot 10^{11}$	&amp; 21		&amp;	26.2\\

\hline

\end{tabular}\caption{Comparison of $N(x)$ and $\log x$}\label{table2}\end{center}

\end{table}

Moreover, with the bound of $N(x)$ proved by K\v r\'i\v zek and al.~\cite{kri} we can now give the following value of the sum $S$ of the series of reciprocals of all elite primes:

\begin{eqnarray}
0.70\leq S \leq 0.74,
\end{eqnarray}
i.e., the first digit after the decimal point is settled.
Our conjectured bound would lead to seven more digits:
\begin{eqnarray}
S=0.700764011 \pm 0.12\cdot 10^{-8}.
\end{eqnarray}


\begin{thebibliography}{9}



\bibitem{aigner}

A. Aigner, \"Uber Primzahlen, nach denen (fast) alle Fermatzahlen quadratische Nichtreste sind,  \textit{Monatsh. Math.} \textbf{101} (1987), 85--93.



\bibitem{guy}

R. K. Guy, \textit{Unsolved Problem in Number Theory}, Springer, 2004.



\bibitem{hardy}

G. H. Hardy, E. L. Wright, \textit{An Introduction to the Theory of Numbers}, Oxford University Press, 1979.



\bibitem{kri2}

M. K\v r\'i\v zek, F. Luca, L. Somer, \textit{17 Lectures on Fermat numbers. From Number Theory to Geometry}, Springer, 2001.



\bibitem{kri}

M. K\v r\'i\v zek, F. Luca, L. Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers. \textit{J. Number Theory} \textbf{97} (2002), 95--112.



\bibitem{muller}

T. M\"uller, Searching for large elite primes, \textit{Experiment. Math.} \textbf{15}:2 (2006), 183--186.



\bibitem{sloane}
N. J. A. Sloane,
\href{http://www.research.att.com/~njas/sequences/}{Online Encyclopedia of Integer Sequences} (OEIS), electronically published at: 
\href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/\char'176njas/sequences/}.



\end{thebibliography}




\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11A15; Secondary 11A41.

\noindent \emph{Keywords: }  elite primes, Fermat Numbers.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A102742}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 18 2006;
revised version received August 21 2006. 
Published in {\it Journal of Integer Sequences}, August 21 2006.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>