\documentclass[12pt,a4paper]{article}
\usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb}

\title{All elite primes up to $250$ billion}
\date{}
\author{Alain Chaumont\footnote{Laboratoire M.S.M., Universit\'e Louis Pasteur, 4, rue B. Pascal, 67000 Strasbourg (France)}\\ and\\ Tom M\"uller\footnote{corresponding author; Institut f\"ur Cusanus-Forschung an der Universit\"at und der Theologischen Fakult\"at Trier, Domfreihof 3, 54290 Trier (Germany), muel4503@uni-trier.de}}

\begin{document}
\maketitle

\begin{abstract}
A prime number $p$ is called elite if only finitely many Fermat numbers $2^{2^n}+1$ are quadratic residues to $p$. So far, only the interval up to $10^9$ was systematically searched for elite primes and 16 such items 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.\\
 \\
MSC 2000: 11A15; 11A41\\
Keywords: Elite Primes, Fermat Numbers 
\end{abstract}

\section{Introduction}
Denote $\{F_n\}$ with $F_n:=2^{2^n}+1$ 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$ elite, if there is an integer index $m$ for which all $F_{n}$ with $n>m$ are quadratic non-residues to $p$, i.e. there is no solution to the congruential equation $x^2 \equiv F_n$ (mod $p$) for $n>m$. Alexander Aigner~\cite{aigner}, who first defined and studied elite primes, discovered 14 such numbers with values less than 35 million. Two further items less than $10^9$ were found by the second author~\cite{muller}. All these items are summarized in Table \ref{tab1}.\\
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(\ln^c(x)\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.
\begin{table}[h]
\begin{center}\begin{tabular}{|c|c|}
\hline
elite primes 	& discovered\\ \hline
3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041,&\\
163841, 544001, 604801, 6684673, 14172161 & Aigner (1986)\\ \hline
159318017, 446960641 & M\"uller (2005)\\
\hline
\end{tabular}\caption{All elite primes $< 10^9$}\label{tab1}\end{center}
\end{table}
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}
Due to 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 congruences $F_n \bmod p$ will become periodic at some point. 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\bmod 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>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 \bmod 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<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 items 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 items 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 items known to date.
\begin{table}[h]
\begin{center}\begin{tabular}{|r|c|}
\hline
$p$ 			&  $L$\\ \hline
1\,151\,139\,841	& 4	\\
3\,208\,642\,561	& 4	\\
38\,126\,223\,361	& 4	\\
108\,905\,103\,361	& 4	\\
171\,727\,482\,881	& 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 A102742~\cite{sloane}.\\
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 $\ln(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$ 			&  $N(x)$	& $\ln(x)$\\ \hline
$10$			& 3		&	2.3\\
$10^2$			& 4		&	4.6\\
$10^5$			& 9		&	11.5\\
$10^6$			& 12		&	13.8\\
$10^9$			& 16		&	20.7\\
$2.5\cdot 10^{11}$	& 21		&	26.2\\
\hline
\end{tabular}\caption{Comparison of $N(x)$ and $\ln(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 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}
Online Encyclopedia of Integer Sequences (OEIS), electronically published at: http://www.research.att.com/\~~njas/sequences/

\end{thebibliography}

\end{document}