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