\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