\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