\documentclass[12pt,reqno]{article}

%\DeclareMathOperator{\ind}{ind}

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

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}



\newtheorem{thm}{Theorem}[]
\newtheorem{conj}{Conjecture}[]
\newtheorem{lem}{Lemma}[section]
\theoremstyle{remark}
\newtheorem{rem}{Remark}[section]
\theoremstyle{definition}
\newtheorem{alg}{Algorithm}[section]

\begin{center}
\vskip 1cm{\LARGE\bf Verifying Two Conjectures on Generalized\\
\vskip .1in Elite
Primes} \vskip 1cm \large
Xiaoqin Li \footnote{Research supported by NSF of China Grant 10726074.}
\\
Mathematics Department \\
Anhui Normal University\\
Wuhu 241000, Anhui\\
People's Republic of China\\
\href{mailto:qinlxss@163.com}{\tt qinlxss@163.com}\\
\href{mailto:lxq623@mail.ahnu.edu.cn }{\tt lxq623@mail.ahnu.edu.cn}\\
\end{center}
\vskip .2 in

\begin{abstract}
 A prime number $p$ is called $b${\it-elite} if only finitely many generalized Fermat
 numbers $F_{b,n}=b^{2^n}+1$ are quadratic residues modulo $p$. Let $p$ be a prime. Write $p-1=2^rh$
 with $r\geq 0$ and $h$ odd. Define the length of the \textit{b-Fermat period of $p$} to be the minimal natural
 number $L$ such that $F_{b,r+L}\equiv F_{b,r}$  (mod $p$).
 Recently M\"uller and Reinhart derived three
 conjectures on $b${\it-elite} primes, two of them being the following. (1) For every natural number $b>1$ there
 is a $b${\it-elite} prime. (2) There are generalized elite primes with elite periods of arbitrarily large lengths. We
 extend M\"uller and Reinhart's observations and computational results to further support above two conjectures. We
 show that Conjecture 1 is true for $b\leq10^{13}$ and that for every possible length
 $1\leq L\leq40$ there actually exists a generalized elite prime with elite period length $L$.

\end{abstract}


\section{Introduction}

The numbers of the form
\begin{eqnarray*}
F_{b,n}=b^{2^n}+1
\end{eqnarray*}
are called generalized Fermat numbers (GFNs) for natural numbers $b$
and $n$. The definition generalizes the usual Fermat numbers
$F_{n}=2^{2^n}+1$, which were named after Pierre Simon de Fermat
(1601-1665). A lot of research has been done on Fermat numbers and
their generalization since then (see \cite{bjorn, dubner0, dubner,
krizek}).

In 1986 Aigner \cite{aigner} called a prime number $p$  {\it elite}
if only finitely many Fermat numbers $F_{n}$ are quadratic residues
modulo $p$, i.e., there is an integer index $m$ for which all
$F_{n}$ with $n>m$ are quadratic non-residues modulo $p$. He
discovered only 14 such prime numbers less than $3.5\cdot 10^7$.
More computational effort yielded all 27 elites up to $2.5\cdot
10^{12}$ together with some 60 much larger numbers \cite{ chaumont,
chaumont1, muller0}. These prime numbers are summarized in sequence
\seqnum{A102742} of Sloane's \textit{On-Line Encyclopedia of Integer
Sequences}~\cite{sloane}.

M\"uller and Reinhart \cite{muller} generalized Aigner's concept of
elite primes in analogy to that of Fermat numbers.

\newtheorem{def1}{Definition}[section]\label{def}
\begin{def1} (\cite[Definition 1.1]{muller}).
Let $p$ be a prime number and $b\geq 2$ be a natural number. Then
$p$ is called a $b${\it-elite} prime if there exists a natural
number $m$, such that for all $n\geq m$ the GFNs $F_{b,n}$ are
quadratic non-residues modulo $p$.
\end{def1}


By the recurrence relation
\begin{eqnarray}\label{rec}
F_{b,n+1}=\left(F_{b,n}-1\right)^2+1,
\end{eqnarray}
one sees that the congruences $F_{b,n}$ (mod $p$) eventually become
periodic. Write $p-1=2^rh$
 with $r\geq 0$ and $h$ odd. Then
this period -- M\"uller and Reinhart \cite{muller} called it
\textit{b-Fermat period of $p$} -- begins at latest with the term
$F_{b,r}$. So there has to be a minimal natural number $L$ such that
\begin{equation} \label{rec1}
F_{b,r+L}\equiv F_{b,r}  \,(\bmod\, p) ,
\end{equation}
which they~\cite{muller} call the \textit{length of the b-Fermat
period} of $p$. The terms $F_{b,n} \,(\bmod\, p)$ for
$n=r,\ldots,r+L-1$ are the \textit{b-Fermat remainders} of $p$.

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


M\"uller and Reinhart \cite{muller} gave fundamental observations on
$b${\it-elite} primes and presented selected computational results
from which three conjectures are derived, two of them being the
following.

\begin{conj}\label{con1}\cite[Conjecture 4.1]{muller}
For every natural number $b>1$ there is a $b${\it-elite} prime.
\end{conj}

\begin{conj}\label{con2}\cite[Conjecture 4.2]{muller}
There are generalized elite primes with elite periods of arbitrarily
large lengths.
\end{conj}

 Concerning Conjecture~\ref{con1}, M\"uller and Reinhart \cite{muller} observed that most of the bases $b$
 actually have the prime $3$ or $5$ as $b${\it-elite} -- only the bases $b\equiv 0$ (mod 15) do not
 belong to one of these two ``trivial" families. Conjecture~\ref{con2} seems to be supported by their
 computations. They \cite{muller} proved the following Lemma \ref{lem11}.

\begin{lem}\label{lem11}
For every
\begin{equation}\label{L1}
L\in \mathcal{L}_1=\{1,2,4,6,8,10,12\},
\end{equation}
there is a generalized elite prime $p<10^4$ with elite period length
$L$.
\end{lem}


The main purpose of this paper is to extend M\"uller and Reinhart's
observations and computational results to give further support to
the two conjectures above. We state our main results as the
 following two Theorems.

 \begin{thm}\label{thm1} Conjecture 1 is true for $1<b\leq 10^{13}$.
 More precisely, for every natural number $1<b\leq 10^{13}$, there is a $b${\it-elite}
 prime $p\leq 472166881$.
 \end{thm}

 \begin{thm}\label{thm2}
 For every $$L\in\{1,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40\},$$ there is a generalized elite prime
  $p\leq100663393$ with elite period length $L$.
 \end{thm}

 In Section $2$ we give an algorithm to test the $b$-eliteness of  $p$ for given $b\geq 2$ and prime $p$. The main
 tool of our algorithm is the Legendre symbol. Comparison of effectiveness with M\"uller's method for
 testing the 2-eliteness of $p$  is given, see Remark \ref{compare}.

 In Section $3$ we prove Theorem 1. We first propose a sufficient and necessary condition on base $b\geq 2$ to which
 there is a $b${\it-elite} prime $p\in \{3,5,7,11,13,19,41,641\}$. Using the condition and the Chinese Remainder Theorem,
 it is easy to compute a set $\mathcal{R}$ with cardinality $|\mathcal{R}|=3667599$ such that Conjecture \ref{con1} is
 already true for those bases $b$ such that $b \,(\bmod\, m) \not\in \mathcal{\mathcal{R}}$, where
 $m=3\cdot5\cdot7\cdot11\cdot13\cdot19\cdot41\cdot641=7497575085$. Thus we only need to consider the bases $b$ with
 $b \,(\bmod\, m) \in \mathcal{\mathcal{R}}.$ We then give an algorithm to find the smallest $b${\it-elite} prime $P_b$ for
 each base $b=um+b_i\leq 10^{13}$ with $b_i\in \mathcal{R}$. At last we tabulate $\overline{P}(B)$ and the smallest $b$
 with $P_b=\overline{P}(B)$ for $B=10^{10},10^{11},10^{12},10^{13},$ where $\overline{P}(B)$ is defined by (\ref{PB2}) in section 3. In
 particular, we have $\overline{P}(10^{13})=472166881=P_{9703200080805}$. Theorem 1 follows.

In Section $4$  we prove Theorem 2. At first we compute all the
elite periods of every generalized elite prime $p< 10^7 $ based on
the method described by M\"uller and Reinhart \cite{muller}. As a
result we find some elite period lengths

\begin{equation}\label{L2}
L\in\mathcal{L}_2=\{14,16,18,20,22,24,26,28,30,36\}.
\end{equation}
For every $L\in\mathcal{L}_2$, we tabulate $P(L)$ and the smallest
$b$ to which $P(L)$ is elite with length $L$, where $P(L)$ is
defined by (\ref{PL}) in section 4. In particular we have
$P(36)=742073 $(the smallest base $b=5369)$. We also give a new
method to find some elite primes with elite period lengths 32,34,38
and 40, where $L=40$ is realized by the elite prime
$p=100663393\,($the smallest base $b=54712)$. Thus Theorem
\ref{thm2} follows.

\section{ A $b$-eliteness testing algorithm}
 Let $b>1$ be an integer, and let $p=2^{\,r}\cdot h+1$ be a prime number with $r\geq 1$ and $h$  odd. In this section,
 we will give an algorithm to test the $b$-eliteness of $p$. Let $\left(\frac{*}{*}\right)$ denote the Legendre symbol.
 Our algorithm is based on the following criterion.
\begin{equation}\label{Criterion_my}
 F_{b,n} ~\text{is a quadratic non-residue modulo}~ p ~\text{if and only if}~\left(\frac{F_{b,n}}{p}\right)=-1.
\end{equation}

Given $b\geq 2$ and prime $p=2^{\,r}\cdot h+1$ with $h$ odd, we
check whether
\begin{equation}\label{rec2}
  \left(\frac{F_{b,n}}{p}\right)=-1
\end{equation}
holds for $n=r,r+1,r+2,\ldots$ consecutively, where $F_{b,n}\,
(\bmod\,p)$ are computed recursively by (\ref{rec}). If (\ref{rec2})
does not hold for some $n\geq r$, then $p$ is not $b${\it-elite}. If
(\ref{rec2}) holds for  $r\leq n\leq r+L-1$, then $p$ is
$b${\it-elite}, where $L$ is the \textit{length of the b-Fermat
period} of $p$, namely the least positive integer such that
(\ref{rec1}) holds.

 Now we describe  our Algorithm \ref{alg1} in the following pseudocode.

\begin{alg}\label{alg1} Testing the $b$-eliteness of prime $p$;

\noindent\{Input $b\geq 2$ and prime $p$\}

 \noindent\{Determine whether $p$ is $b${\it-elite} or not; if $p$ is $b${\it-elite} then output the length $L$\}

\noindent {\bf Begin}  Finding $r$ and $h$ such that $p= 2^{r}h+1$
with $h$ odd;

 $f_{b}\leftarrow F_{b,r} \,(\bmod\, p)$; $f \leftarrow f_{b}$;
 $L\leftarrow 0$; $elite \leftarrow~ True$;

 {\bf Repeat} Computing $\left(\frac{f_{b}}{p}\right)$ by \cite[Algorithm 2.3.5]{CP} (cf. also \cite[\S11.3]{Rosen});

 \hspace{4mm} {\bf If }
 $\left(\frac{f_{b}}{p}\right)\neq -1$ {\bf Then } $elite \leftarrow False$  {\bf Else}

 \hspace{8mm} {\bf begin} $f_{b}\leftarrow(f_{b}-1)^{2}+1 \,(\bmod\, p)$; $L\leftarrow L+1$  {\bf  end};


 {\bf Until }  ({\bf not} $elite$) {\bf or }$(f_b=f)$;

 {\bf If} $elite$ {\bf Then} output $L$ {\bf Else} output ``$p$ is not $b$-elite''

\noindent {\bf End}.
\end{alg}

\begin{rem} The prime $2$ is not
$b${\it-elite} to any $b\geq 2$ since there is no quadratic
non-residue modulo $2$. So here and for the rest of this paper, we
only need to consider odd primes $p$.
\end{rem}

\begin{rem}\label{compare}
 Let $q$ be a prime and $c$ be a positive integer with $q \nmid c$. Denote by ord$_{q}(c)$ the multiplicative order of
 $c \,(\bmod\,p)$. M\"uller \cite{muller0} gave an eliteness testing algorithm \cite[Algorithm 3.1]{muller0} for the base
 $b=2$ based on the following   criterion \cite[Theorem 2.1]{muller0}.
\begin{equation}\label{Criterion_muller}
 F_{2,n}~ \text{is a quadratic non-residue modulo}~ p ~\text{if and only if}~ 2^{\,r} \mid \text{ord}_{p}(F_{2,n}).
\end{equation}
 To check whether $2^{\,r}$ divides ord$_{p}(F_{2,n})$ for $n=r,r+1,r+2,\ldots$, the algorithm computes
 $F_{2,n}^{2^{k}h} \,(\bmod\, p)$ for $k=0,1,\ldots,k_{0}$, where $k_{0}=\min \{0\leq k \leq r:
 F_{2,n}^{2^{k}h}\equiv 1  \,(\bmod\, p)\}$. It is well-known \cite[\S 2.1.2]{CP} (see also \cite[Theorem 4.9]{Rosen}) that
 it takes $$O(\ln s\cdot \ln^{2}p)$$
 bit operations to compute the modular exponentiation $F_{2,n}^{\,s}\,(\bmod\, p)$. With our method, we
 compute the Legendre symbol $\left(\frac{F_{2,n}}{p}\right)$, which requires only $$O(\ln^{2}p)$$
  bit operations \cite[\S 2.3]{CP} (see also \cite[Corollary 11.12.1 and Exerice
  11.3.16]{Rosen}). So, for testing the $b$-eliteness of $p$, using criterion (\ref{Criterion_my}) is
  faster than using criterion (\ref{Criterion_muller}).
\end{rem}

\section{Proof of Theorem 1}
 Throughout this section, let $\mathbb{N} = \{0,1,2,3,\ldots \}$ be the set of all  natural
 numbers. Let $\mathcal{B}\subset \mathcal{A}$ be two sets. We denote by $|\mathcal{A}|$ the number of elements
in $\mathcal{A}$, and
 $$\mathcal{A} - \mathcal{B}=\{c:c\in \mathcal{A}, c\not\in\mathcal{B}\}.$$
  Let $p$ be an odd prime. Define the sets
 $$\mathcal{A}_{p}= \{0,1,2,\ldots, p-1\};$$
 $$\mathcal{B}_{p}=
 \begin{cases}
   \{b(\geq 2)\in \mathcal{A}_{p}: p \text{ is}~ b \text{\it-elite} \}\cup\{1\}, &\text{if} ~p ~\text{ is} ~(p-1)
   \text{{\it-elite}};\\
  \{b(\geq 2)\in \mathcal{A}_{p}: p \text{ is}~ b \text{\it-elite} \},&\text{if} ~p ~\text{ is not} ~(p-1)
  \text{{\it-elite}};
  \end{cases}$$
and
$$ \mathcal{R}_{p}=\mathcal{A}_{p} - \mathcal{B}_{p}.$$


To prove Theorem \ref{thm1}, we need nine Lemmata.

\begin{lem}\label{lem1}\cite[Observation 2.2,2.3]{muller}
 Let $p$ be an odd prime number, $b$ be a natural number. If $p$ is $b${\it-elite}, then

(1) $p$ is $(b+pk)${\it-elite} for $k\in \{a,a+1,a+2,\ldots\}$,
where $a=\lceil \frac{-b}{p}\rceil$;

(2) $p$ is $(p-b)${\it-elite} if $2\leq b< p$.

Moreover, the Fermat remainders and the respective length of the
Fermat period for the bases $b+pk$ and $p-b$ are the same.
\end{lem}


By Lemma \ref{lem1} we have
\begin{lem}\label{lem4}
 Let $p$ be an odd prime and $\;b\,(>1)\in\mathbb{N}$. Then
 $$p \text{ is } b \text{-elite if and only if } b\; (\bmod\; p)\in \mathcal{B}_{p}.$$

\end{lem}


\begin{lem}\cite[Consequence 2.10]{muller}\label{lem0}
We have $\mathcal{R}_{3}=\mathcal{R}_{5}=\{0\}$.
\end{lem}

\begin{lem}\label{lem2}\cite[Theorem 2.13]{muller}
Let $b$ be a natural number and $p$ be an odd prime number. Then $p$
is $b${\it-elite} with $L=2$ if and only if $p\equiv 7 \,(\bmod\,
12)$ and either $b^2+1\equiv b \, (\bmod\, p)$ with
$\left(\frac{b}{p}\right)=-1$ or $b^2+1\equiv -b\,(\bmod\, p)$ with
$\left(\frac{b}{p}\right)=1$.
\end{lem}

\begin{lem}\label{lem3}
We have $\mathcal{R}_{7}=\{0,1,6\}$.
\end{lem}

\begin{proof} Let  $k\in
\{0,1,2,3,4,5,6\}$. Then

$$ k^{2}+1\; (\text{mod } 7)=
 \begin{cases}
  k, \noindent\hspace{8mm} &if ~~k= 3,5;\\
  7-k,\noindent\hspace{4mm} &if ~~k= 2,4;\\
  1, \noindent\hspace{8mm} &if ~~k=0 ;\\
  2, \noindent\hspace{8mm} &if ~~k= 1,6;\\
  \end{cases}$$
and
$$ \left(\frac{k}{7}\right)=
 \begin{cases}
  1,\noindent\hspace{8mm} &if ~~k= 1,2,4;\\
  0,\noindent\hspace{8mm} &if ~~k= 0;\\
  -1, \noindent\hspace{4mm} &if ~~k= 3,5,6;\\
  \end{cases}$$


Based on Lemma~\ref{lem2}, we have $\mathcal{B}_{7}=\{2,3,4,5\}.$
Thus the Lemma follows.
\end{proof}



 Using Algorithm~\ref{alg1}, we can easily get the following Lemma~\ref{lem6} and Lemma~\ref{lem61}.

\begin{lem}\label{lem6}
We have
 $$\mathcal{R}_{11}=\{0,2,3,4,5,6,7,8,9\}; \mathcal{R}_{13}=\{0,2,3,4,6,7,9,10,11\};$$
 $$\mathcal{R}_{19}=\{0,2,3,4,5,6,9,10,13,14,15,16,17\};$$
$$\mathcal{R}_{17}=\mathcal{A}_{17} \text{ and }\mathcal{R}_{23}=\mathcal{A}_{23}.$$
\end{lem}

\begin{lem}\label{lem61}
Let $p<1000$ be an odd prime. Then
 $$|\mathcal{R}_p|< \frac12|\mathcal{A}_p| \text{ if and only if } p\in\{3,5,7,41,641\},$$
where
  $$\mathcal{R}_{41}=\{0,1,3,9,14,27,32,38,40\}$$ and

  $\mathcal{R}_{641}= \{0,1,2,4,5,8,10,16,20,21,25,29,31,32,40,42,50,58,61,62,64,67,77,$

~~~~~~~~~~~$80,84,100,105,116,122,124,125,128,129,134,141,145,153,154,155,$

~~~~~~~~~~~$159,160,168,177,199,200,210,221,232,241,243,244,248,250,256,258,$

~~~~~~~~~~~$268,282,287,290,305,306,308,310,318,320,321,323,331,333,335,336,$

~~~~~~~~~~~$351,354,359,373,383,385,391,393,397,398,400,409,420,431,441,442,$

~~~~~~~~~~~$464,473,481,482,486,487,488,496,500,507,512,513,516,517,519,525,$

~~~~~~~~~~~$536,541,557,561,564,574,577,579,580,583,591,599,601,609,610,612,$

~~~~~~~~~~~$616,620,621,625,631,633,636,637,639,640\}.$
\end{lem}

\begin{rem}
 In fact, the two results ``$\mathcal{R}_{17}=\mathcal{A}_{17}$" and
 ``$\mathcal{R}_{23}=\mathcal{A}_{23}$" were already given by M\"uller and Reinhart~\cite{muller}
 where they are immediate consequences of Theorem 2.15 and Theorem
 2.16. By Lemma \ref{lem6} and Lemma \ref{lem1}, the primes $17$ and $23$ are
 not $b${\it-elite} to any natural number $b\geq 2$.
\end{rem}


Let
\begin{equation}\label{m}
m=3\cdot5\cdot7\cdot11\cdot13\cdot19\cdot41\cdot641=7497575085.
\end{equation}
 Applying the Chinese Remainder Theorem, it is easy to compute the set
\begin{equation}\label{setR}
 \mathcal{R}=\left\{0\leq b<m: b\; (\bmod p) \in  \mathcal{R}_{p} \text{ for } p=3,5,7,11,13,19,41,641 \right\}
\end{equation}
 which has cardinality
\begin{equation}\label{Card_R}
 R=|\mathcal{R}|=1\cdot1\cdot3\cdot9\cdot9\cdot13\cdot9\cdot129=3667599.
\end{equation}
 Using the Heap Sort Algorithm~\cite[\S8.3]{Press}, we sort the elements of $\mathcal{R}$ in an increasing order
\begin{equation}\label{sorted_setR}
\mathcal{R}=\{b_1<b_2<\cdots<b_R\},
\end{equation}
where
$$b_1=0, b_2=1590, b_3=2955, b_4=5685, b_5=6405, b_6=7020,\ldots,b_{R}=7497573495.$$

By Lemma \ref{lem4} and the Chinese Remainder Theorem we have the
following Lemma \ref{lem38}.

\begin{lem}\label{lem38}
 Let $b\,(>1)\in \mathbb{N}$, and let $m$ be given as in (\ref{m}). Then

 there is a $b${\it-elite} prime $p\in \{3,5,7,11,13,19,41,641\}$

 $\text{ if and only if } b \,(\bmod\, p) \in \mathcal{B}_p \text{ for some } p\in\{3,5,7,11,13,19,41,641\}$

 $\text{ if and only if } b \,(\bmod\, m) \not\in \mathcal{\mathcal{R}}.$
\end{lem}

 From Lemma \ref{lem38}, we see that Conjecture \ref{con1} is already true for
 those bases $b$ such that $b \,(\bmod\, m) \not\in \mathcal{\mathcal{R}}$. Thus we only need to consider the bases
 $b$ with $b \,(\bmod\, m) \in \mathcal{\mathcal{R}}.$

 \begin{lem}\label{lem39}
 For every base $1<b\leq 10^{13}$ with $b\, (\bmod\, m)\in \mathcal{R}$, there is a
 prime $p\leq 472166881$ such that $p$ is $b$-elite.
\end{lem}
 \begin{proof}
 Given $b\geq 2$ with $b \,(\bmod\,m)\in \mathcal{R}$, let
\begin{equation}\label{setPb}
 \mathcal{P}_{b} = \{\text{prime } p: p\text{ is } b\text{-elite}\},
\end{equation}
and let
\begin{equation}\label{Pb}
 P_{b} = \begin{cases}\infty, &\text{if }\mathcal{P}_{b}=\emptyset,\\
                       \min\{p: p\in \mathcal{P}_{b}\},&\text{otherwise}.\\
         \end{cases}
\end{equation}

 Let $1\leq B_1<B_2$ be two natural numbers such that
 $$\mathcal{R}\cap \{b \,(\bmod\,m): B_1<b\leq B_2\}\neq \emptyset.$$
Define the functions
\begin{equation}\label{PB1B2}
 \overline{P}(B_1,B_2)=\max\{P_{b}:B_1< b \leq B_2, b\, (\bmod\, m)\in\mathcal{R}\},
\end{equation}
and
\begin{equation}\label{PB2}
 \overline{P}(B_2)=\overline{P}(1,B_2)=\max\{\overline{P}(1,B_1),\overline{P}(B_1,B_2)\},
\end{equation}

 With the above preparation, we describe our algorithm for verifying Lemma \ref{lem39} for those bases $b$ with
 $B_1< b \leq B_2$ and $b\, (\bmod\, m)\in\mathcal{R}$.

\begin{alg}\label{alg3}  Verifying Lemma \ref{lem39} for $B_1<b\leq B_2$ with $b\,(\bmod\, m)\in\mathcal{R}$;

 \noindent\{Input $B_1,B_2$ and $maxp$ with $1\leq B_1<B_2,$ say $B_1=10^{10}$, $B_2=10^{11}$, and $maxp=10^9$\}

  \noindent\{Output either $\overline{P}=\overline{P}(B_1,B_2)<maxp$ and the smallest $b\in (B_1,B_2]$ such that
 $\overline{P}=P_b$\}

 \noindent\{or the smallest $b\in (B_1,B_2]$ with $b\,(\bmod\, m)\in\mathcal{R}$ such that Lemma \ref{lem39} fails\}

\noindent {\bf Begin} $\overline{P}\leftarrow 3 $;
 $u \leftarrow \lfloor\frac{B_1}{m}\rfloor \cdot m$; $b' \leftarrow u$; $j\leftarrow 1$; $First \leftarrow True$;

{\bf While} $b'\leq B_1$ {\bf Do begin} $j \leftarrow j+1$; $b'
\leftarrow u+b_j$ {\bf end};


 {\bf Repeat If} $First$ {\bf Then begin} $i \leftarrow j$; $First \leftarrow False$ {\bf end  Else} $i \leftarrow 0$ ;

 \hspace{4mm}
 {\bf repeat}  $p\leftarrow 29$; $Found \leftarrow False$;

  \hspace{8mm}
  {\bf Repeat} $b''\leftarrow b' \,(\bmod\,p)$;

  \hspace{12mm} Using Algorithm \ref{alg1} to test the $b''$-eliteness of $p$;

 \hspace{12mm} {\bf If} $p$ is $b''$-elite {\bf Then}

 \hspace{16mm} {\bf begin} $Found \leftarrow~ True$; {\bf If} $p>\overline{P}$ {\bf Then
 Begin} $\overline{P}\leftarrow p$; $b\leftarrow b'$ {\bf End}

 \hspace{16mm} {\bf end~~~~~~~~~~Else}

 \hspace{16mm}{\bf begin} $p\leftarrow $ the next prime $>p$;

 \hspace{20mm} {\bf If} ($p=41$) or ($p=641$) {\bf then} $p\leftarrow $ the next prime $>p$

 \hspace{16mm}{\bf end}

 \hspace{8mm} {\bf Until} $Found$ {\bf Or} $(p>maxp)$;

 \hspace{8mm}  {\bf If} not $Found$  {\bf Then}

 \hspace{12mm} {\bf begin} output ``the lemma fails at $b'$, enlarge $maxp$ and try again''; exit

 \hspace{12mm} {\bf end};

  \hspace{8mm} $i \leftarrow i+1$;  $b' \leftarrow u+b_i$;

 \hspace{4mm} {\bf until} $(i>R)$ or $(b'>B_2)$;

 \hspace{4mm} $u \leftarrow u+m$;

 {\bf Until} $u >B_2$;

Output $\overline{P}$ and $b$;

\noindent  {\bf End};
\end{alg}

 The Delphi program ran about $105$ hours on a PC AMD 3000+/2.0G to find
 $$\overline{P}(1, 10^{10}),\;\overline{P}(10^{10}, 10^{11}),\;\overline{P}(10^{11}, 10^{12}), $$
 and
 $$\overline{P}(i\cdot 10^{12}, (i+1)\cdot 10^{12}),\; \text{for}\; i=1,2,\ldots,9.$$
 Then by (\ref{PB2}) we  get $\overline{P}(B)$ for $B=10^{10}, 10^{11},  10^{12}, 10^{13}$; see Table \ref{table1},
 where $b$ is the first base with $P_b=\overline{P}(B)$.
 As a result we have $$\overline{P}(10^{13})=472166881,$$ which means that for every base $1<b\leq10^{13}$ with
 $b\, (\bmod\, m)\in \mathcal{R}$, there is a prime $p\leq 472166881$ such that $p$ is
 $b$-elite. The Lemma follows.
\end{proof}

 Lemma \ref{lem39} together with Lemma \ref{lem38} implies Theorem \ref{thm1}.

\begin{table}[H]
 \caption{$\overline{P}(B) \text{ and } b$ with $P_b=\overline{P}(B)$}\label{table1}
\begin{center}\begin{tabular}{|c|r|r|r|r|r|}

\hline
 $B$ & $10^{10}$   & $10^{11}$ & $10^{12}$ & $10^{13}$   \\

\hline
$\overline{P}(B)$  &   5483521      &  24494081&   167772161 & 472166881        \\

\hline$b$ &   4157043150    &  45329209185 & 224199632355 & 9703200080805  \\
\hline$L$ &   4   &  12 & 4 & 4  \\

\hline
\end{tabular}
\end{center}
\end{table}

\section{Proof of Theorem 2}
Let $L\in\{1,2,4,6,8,\ldots\}$. Define

\begin{equation}\label{setPL}
 \mathcal{P}(L) = \{\text{prime } p: p ~~\text{is a generalized elite with
period length} ~~L\}
\end{equation}
and let
\begin{equation}\label{PL}
 P(L) = \begin{cases}\infty, &\text{if }\mathcal{P}(L)=\emptyset,\\
                       \min\{p: p\in \mathcal{P}(L)\},&\text{otherwise}.\\
         \end{cases}
\end{equation}



 By Lemma \ref{lem11}, M\"uller and
Reinhart~\cite{muller} have found $P(L)$ for
$L\in\mathcal{L}_1$($\mathcal{L}_1$ is given by (\ref{L1})). We
summarize their computations in the following Table~\ref{table2},
where $b$ is the base to which $P(L)$ is elite with elite period
length  $L$.
\begin{table}[H]
\caption{The function $P(L)$ for $L\in\mathcal{L}_1$}\label{table2}
\begin{center}\begin{tabular}{|c|r|r|r|r|r|r|r|r|}

\hline
 $L$ & ~~~~1& ~~~~2& ~~~~4  & ~~~~6 & ~~~~8 & ~~10 & ~~12 \\

\hline
$P(L)$  &  3    & 7     &   41        &   199 &  409  & 331 & 3121         \\

\hline$ b $ & 2 & 2 &  2   &   19     & 6   & 23   & 8       \\

\hline

\end{tabular}
\end{center}
\end{table}


To prove Theorem \ref{thm2}, we need three Lemmata.


\begin{lem}\label{lem42}\cite[Theorem 2.18]{muller}
Let $p = 2^r h+1$ with $h$ odd. Let $n$ be the number of all
possible periods and denote by $L_i$ the length of the period $i$.
Then
\begin{eqnarray}
\sum_{i=1}^n L_i = h.
\end{eqnarray}
The number $N_{b,i}$ of all $b$'s in the period $i$ is
\begin{eqnarray}
N_{b,i} = 2^r\cdot L_i.
\end{eqnarray}
\end{lem}

\begin{lem}\label{lem43}
For every
 $L\in\mathcal{L}_2$ ($\mathcal{L}_2$ is given by (\ref{L2})),
 there is a generalized elite prime $p<10^7$
 with elite period length $L$.
\end{lem}

\begin{proof}
Based on Lemma \ref{lem42}, M\"uller and Reinhart~\cite{muller}
presented an algorithm to find the first elite period of prime $p$.

Given a prime $p=2^{\,r}\cdot h+1$ with $h$ odd, let

\begin{equation}\label{Sp}
\mathcal{S}_{2^r}=\{c\in
\mathbb{Z}_p:\exists~b\in\mathbb{Z}_p~\text{such that}~b^{2^r}\equiv
c\,(\bmod\,p)\}.
\end{equation}
 Then we have $|\mathcal{S}_{2^r}|=h$ and

\begin{equation}\label{c}F_{b,n}-1\,(\bmod\,p) \in\mathcal{S}_{2^r}\end{equation}
 for $n=
r,\ldots,r+L-1$ and for all bases $b$. Moreover, elements of
$\mathcal{S}_{2^r}$ belong to many different periods of various
lengths.

Let $g$ be a primitive root modulo $p$ and let $c\in
\mathcal{S}_{2^r}.$ Then we have $c=g^{2^rk_0}$ with
$k_0\in\{0,1,\ldots,h-1\}.$ Let $g_0=g^{k_0}$. We check whether
\begin{equation}\label{recg}
  \left(\frac{g_0^{2^{r+i}}+1}{p}\right)=-1
\end{equation}
holds for $i=0,1,2,\ldots$ consecutively. If (\ref{recg}) does not
hold for some $i$, then this Fermat period is not an elite period.
If (\ref{recg}) holds for $0\leq i <l$, where $l$ is the smallest
natural number such that $g_{0}^{2^{\,r+l}}\equiv
g_{0}^{2^{\,r}}(\bmod\,p)$, then the period
$c+1,c^{2}+1,\ldots,c^{2^{l-1}}+1$ is an elite period with length
$L=l$.

It is easy to modify M\"uller and Reinhart's computational method in
order to find all elite periods of every generalized elite prime $p
< Bound$, say $Bound=10^7$. Now we describe the modified algorithm
in the following pseudocode.

\begin{alg}\label{alg2} Finding all elite periods $L$ of each prime $p <
Bound$ if they exist.

\{Input $Bound$, say $Bound=10^7$; Output $p<Bound$ with $L>12$.\}

\noindent  {\bf Begin}  $p\leftarrow 3$;

{\bf Repeat} Finding $r$ and $h$ such that $p= 2^{r}h+1$ with $h$
odd; $g \leftarrow $~primitive root $\bmod ~p$;

\hspace{8mm} {\bf For} $i \leftarrow  0$ {\bf To} $h $ {\bf Do}
$tested_{i} \leftarrow ~ False$; $periodstart\leftarrow 0$;

\hspace{8mm} {\bf repeat} $index\leftarrow ~periodstart$; $ elite
\leftarrow True$; $L\leftarrow 0 $;

\hspace{12mm} {\bf Repeat} $tested_{index} \leftarrow ~True$; {\bf
If }$elite$ {\bf Then}

\hspace{18mm}{\bf begin } $f \leftarrow g^{2^{r}*index}+1 \,(\bmod\,
 p)$;


\hspace{20mm}Computing $\left(\frac{f}{p}\right)$ by \cite[Algorithm
2.3.5]{CP} (cf. also \cite[\S11.3]{Rosen});

 \hspace{20mm} {\bf If}
$\left(\frac{f}{p}\right)\neq -1$ {\bf Then} $elite \leftarrow~
False$;

\hspace{18mm}{\bf end; }

\hspace{16mm} $index \leftarrow index*2 \,(\bmod\,h)$; $L\leftarrow
L+1$ ;

\hspace{12mm} {\bf Until} $(index=periodstart)$;

\hspace{12mm} {\bf If} $elite$ {\bf and} $(L>12)$ {\bf Then} output
$p~\text{and}~L$;

\hspace{12mm} {\bf While} $tested_{periodstart}$ {\bf Do}
$periodstart\leftarrow~ periodstart+1$;

\hspace{8mm}  {\bf until} $( periodstart=h)$;

\hspace{8mm} $p\leftarrow $ the next prime $>p$ ;

{\bf Until} $p > Bound$


\noindent  {\bf End}.
\end{alg}

The Dephi program ran about $53$ hours to compute all elite periods
of every elite prime $p<10^7$, and find some elite period lengths
$L\in\mathcal{L}_2.$ For every $L\in\mathcal{L}_2$, we summarize
$P(L)$ and the smallest $b$ to which $P(L)$ is elite with length $L$
in Table~\ref{table3}. The Lemma follows.
\end{proof}

\begin{table}[H]
\caption{The function $P(L)$ for $L\in\mathcal{L}_2$}\label{table3}
\begin{center}\begin{tabular}{|c|r|r|r|r|r|r|r|r|r|r|r|}

\hline
 $L$ & 14  & 16  &  18  & 20  & 22 & 24& 26 & 28& 30& 36\\

\hline
$P(L)$  &  32251 & 30841 &   17443  &   36901 &  50543 & 688297  &   180247 & 117973  & 796387 & 742073      \\

\hline$ b $ & 247 & 75 &726 & 298 & 182& 2935& 6143 & 432 & 27867& 5369   \\

\hline

\end{tabular}
\end{center}
\end{table}


\begin{rem}  The smallest base $b$ in Table~\ref{table3} can be easily obtained by using Algorithm \ref{alg1} to
 test the $b$-eliteness of $P(L)$ for $b= 2,3,\ldots,\frac{P(L)-1}{2}$ consecutively until the length of the elite
 period  is found to be $L$.
\end{rem}
\begin{rem}
There are no generalized elite primes $p<10^7$ with  $L=32$ or 34 or
$L>36$.
\end{rem}

 In the following Table~\ref{table4}, we list the factorization of $2^{\frac{L}{2}}+1$ and  the factorization of $P(L)-1$ for
 $L\in\mathcal{L}_3=\{2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,36\}$
\begin{table}[H]
\caption{The factorizations of $2^{\frac{L}{2}}+1$ and of $P(L)-1$
for $L\in\mathcal{L}_3$ }\label{table4}
\begin{center}\begin{tabular}{|c|r|r|r|}

\hline
 $L$ & $P(L)$  & \text{The factorization of} $2^{\frac{L}{2}}+1$   & \text{The factorization of} $P(L)-1$  \\
\hline
2  &  7 & 3 &   $2\cdot3$         \\
4  &  41 & 5 &   $2^3\cdot5$         \\
6  &  199 & $3^2$ &   $2\cdot3\cdot11$         \\
8  & 409 & 17 &   $2^3\cdot3\cdot17$         \\
10  &  331 & $3\cdot11$ &   $2\cdot3\cdot5\cdot11$         \\
12  &  3121 & $5\cdot13$ &   $2^4\cdot3\cdot5\cdot13$         \\
14  &  32251 & $3\cdot43$ &   $2\cdot3\cdot5^3\cdot43$         \\
16  & 30841 & 257  & $2^3\cdot3\cdot5\cdot257$    \\
18   & 17443  &  $3^3\cdot19$ & $2\cdot3^3\cdot17\cdot19$       \\
20   &  36901 &  $5^2\cdot41$ & $2^2\cdot3^2\cdot5^2\cdot41$       \\
22  &  50543 & $3\cdot683$   &  $2\cdot37\cdot683$      \\
24   & 688297  &  $17\cdot241$ & $2^3\cdot3\cdot7\cdot17\cdot241$       \\
26    &  180247 & $3\cdot2731$  & $2\cdot3\cdot11\cdot2731$     \\
28   & 117973  & $5\cdot29\cdot113$ & $2^2\cdot3^2\cdot29\cdot113$      \\
30    & 796387 & $3^2\cdot11\cdot331$  &  $2\cdot3\cdot331\cdot401$  \\
36   & 742073 & $5\cdot13\cdot37\cdot109$  & $2^3\cdot23\cdot37\cdot109$  \\
\hline

\end{tabular}
\end{center}
\end{table}
Let $L$ be even. Define
 $$q_L= \max\{\text{prime}\,q: q\mid2^{\frac{L}{2}}+1\}.$$
Then for every  $L\in\mathcal{L}_3$, we find that,

\begin{equation}\label{rec3}
q_L \mid (P(L)-1).
\end{equation}

Based on~(\ref{rec3}), we try to find some generalized elite primes
$p$ with elite period lengths 32,34,38 and 40. The method is as
follows (taking $L=32$ for example). Since
$2^{\frac{L}{2}}+1=2^{16}+1= 2^{2^4}+1=65537=F_4$, we have
$q_{32}=65537$. In order to find the elite prime $p$ with length 32,
we consider primes $p\,(p>10^7)$ which can be written in the form
$p=65537k+1$ with $k$ an integer. Using Algorithm \ref{alg2}, we
compute all the elite periods of these elite primes consecutively
until the length of the elite period is $L$. As a result we find
that prime $47710937$ is $b${\it-elite} with $L=32$, where $
b=62792$ and $47710936=2^3\cdot7\cdot13\cdot65537$.

In Table~\ref{table5},  for $L=32,34,38$ and 40, we tabulate the
prime $p$, the base $b$ to which $p$ is elite with length $L$.

\begin{table}[H]
\caption{ Elite primes $p$ with length $L=32,34,38$ and
40}\label{table5}
\begin{center}\begin{tabular}{|c|r|r|r|r|}

\hline
 $L$ & $p$ & $b$ & \text{The factorization of} $2^{\frac{L}{2}}+1$   & \text{The factorization of} $p-1$  \\
\hline

32    & 47710937 & 62792 & 65537  & $2^3\cdot7\cdot13\cdot65537$     \\
34  & 51118471  & 106257 & $3\cdot43691$ & $2\cdot3^2\cdot5\cdot13\cdot43691$      \\
38   & 78643351 & 661362 & $3\cdot174763 $  &  $2\cdot3^2\cdot5^2\cdot174763$  \\
40  & 100663393 & 54712 & $17\cdot61681$  & $2^5\cdot3\cdot17\cdot61681$  \\
\hline

\end{tabular}
\end{center}
\end{table}

\begin{rem}
 For every $L\in\{32,34,38,40\}$, the prime $p$ we find in Table~\ref{table5} may be larger than
$P(L)$.
\end{rem}

From Table~\ref{table5}, we have the following Lemma~\ref{lem44}.
\begin{lem}\label{lem44}
 For every $$L\in\{32,34,38,40\},$$ there is a generalized elite
 prime $p\leq 100663393$
 with elite period length $L$.
\end{lem}


Theorem \ref{thm2} follows from Lemma \ref{lem11}, Lemma \ref{lem43}
and Lemma \ref{lem44}.

We have known that for each even $L\leq 40$, there is a generalized
elite prime $p$ with elite period length $L$ such that $q_L \mid
(p-1).$ But it is still an open problem whether for every even $L$
there is a generalized elite prime $p$ with elite period length $L$
such that $q_L \mid (p-1).$

\section{Acknowledgement}
 We thank the referee for kind and helpful comments that improve the
 presentation of the paper.

\begin{thebibliography}{99}

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

\bibitem{bjorn}
A. Bj\"orn and H. Riesel, Factors of generalized Fermat numbers.
\textit{Math. Comp.} \textbf{67} (1998), 441--446.

\bibitem{chaumont}
A. Chaumont and T. M\"uller, All elite primes up to 250 billion.
\textit{J. Integer Seq.} \textbf{9} (2006), Article 06.3.8.

\bibitem{chaumont1}
A. Chaumont, J. Leicht, T. M\"uller and A. Reinhart, The continuing
search for large elite primes. \textit{Int. J. Number Theory.}
\textbf{5} (2009), 209--218.


\bibitem{CP}  R. Crandall and C. Pomerance, \textit{Prime Numbers, a Computational Perspective}, 2nd ed.,
 Springer-Verlag, 2005. %\MR{2156291 (2006a:11005)}


\bibitem{dubner0}
H. Dubner and Y. Gallot, Distribution of generalized Fermat prime
numbers. \textit{Math. Comp.} \textbf{71} (2001), 825--832.

\bibitem{dubner}
H. Dubner and W. Keller, Factors of generalized Fermat numbers.
\textit{Math. Comp.} \textbf{64} (1995), 397--405.


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

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

\bibitem{muller}
T.M\"uller and Andreas Reinhart, On generalized elite primes.
 \textit{J. Integer Seq.} \textbf{11} (2008), Article 08.7.25.

\bibitem{Press}
H. Press, A. Teukolsky, T. Vetterling and P. Flannery,
\textit{Numerical Recipes in C++. The Art of Computer Programming},
Cambridge University Press, 2002.

\bibitem{Rosen}
H. Kenneth Rosen, \textit {Elementary Number Theory and its Applications},
 Addison-Wesley, Fourth edition, 2000.

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


\end{thebibliography}



\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: }  generalized elite primes, generalized Fermat numbers, $b$-Fermat periods.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip


\noindent Received  January 5 2009; revised version received  June 4
2009.  Appeared in {\it Journal of Integer Sequences}, June 20 2009.

\bigskip
\hrule
\bigskip

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


\end{document}%Wednesday, April 8, 2009 at 15:47