\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 On Anti-Elite Prime Numbers
}
\vskip 1cm
\large
Tom M\"uller\\
Institut f\"ur Cusanus-Forschung \\
an der Universit\"at und der Theologischen Fakult\"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}
An odd prime number $p$ is called anti-elite if only finitely many
Fermat numbers are quadratic non-residues to $p$. This
concept is the exact opposite to that of elite prime numbers. We study
some fundamental properties of anti-elites and show that there are
infinitely many of them. A computational search among all the numbers
up to 100 billion yielded 84 anti-elite primes.
\end{abstract}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\section{Introduction}
Let $F_n:=2^{2^n}+1$ be the sequence of Fermat numbers.
In recent research some effort has been spent on so-called elite
primes. A prime number $p$ is called \textit{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 congruence
$x^2 \equiv F_n$ (mod $p$) for $n>m$.
Aigner~\cite{aigner}, who first defined and studied elite primes,
discovered 14 such numbers between 1 and 35 million. More computational
effort yielded all 27 elites up to $2.5\cdot 10^{12}$ together with
some 60 much larger numbers~\cite{muller,chaumont,chaumont1}.
Despite these results, the question whether there are
infinitely many such numbers remains open.
The opposite concept of elite primes is the following. An odd prime number $p$ is called \textit{anti-elite} if only finitely many Fermat numbers are quadratic non-residues modulo $p$. 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$ (mod
$p$) will become periodic at some point. Aigner showed that for any
prime number written in the form $p=2^rh+1$ with $r\in\mathbb{N}$ and
$h > 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$). $L$ can be computed in the following way. The multiplicative
order of 2 modulo $p$ is of the form $2^sk$ with $0\leq s \leq r$ and
$k$ a divisor of $h$. Then $L$ is the multiplicative order of 2 modulo
$k$, i.e., $2^L\equiv 1$ (mod $k$).~\cite{aigner}
The terms $F_{r+\nu}$ (mod $p$) with $\nu=0,\ldots,L-1$ are called \textit{Fermat remainders} of $p$. Therefore, a prime number $p$ is anti-elite if and only if all $L$ Fermat remainders are quadratic residues modulo $p$.
Moreover, it is easy to see that against the concept of elites there is no necessary condition on the parity of $L$. That $L$ has to be smaller than $\frac{p-1}{4}$ is still true (compare Aigner~\cite[pp.\ 89 et seq.]{aigner}).
By partly adapting the proof given by K\v r\' i\v zek, Luca and Somer~\cite{kri} for elites we find that the number $N(x)$ of all anti-elite primes less than or equal to $x$ is asymptotically bounded by
\begin{eqnarray}\label{ass}
N(x)=O\left(\frac{x}{(\log x)^2}\right),
\end{eqnarray}
i.e., the series $S$ of the reciprocals of all anti-elite primes is convergent. In the following section we will deal with some fundamental properties of anti-elite prime numbers. We show, inter alia, that there are infinitely many anti-elite primes. In addition to these theoretic results we computed all anti-elite primes up to $10^{11}$.
\section{Theoretical Results}
\newtheorem{theo001}{Theorem}[section]
\begin{theo001}\label{t01}
Let $p>5$ be a prime number. Then $p$ is a divisor of a Fermat number $F_n$ with $n\geq 2$ if and only if $p$ is anti-elite with $L=1$.
\end{theo001}
\begin{proof}
Let $p$ be a prime factor of $F_n$ with $n\geq 2$. If $p=F_n$, then equation (\ref{one}) implies
\begin{eqnarray}
F_m\equiv 2 \quad (\bmod\, F_n)
\end{eqnarray}
for all $m>n$ and we get $\left(\frac{F_m}{F_n}\right)=1$ since $F_n\equiv 1$ (mod 8). If $F_n$ is not prime, all of its prime divisors have the form $p=2^{n+2}k+1$ with a natural number $k>1$. Here again, we get from (\ref{one}) that
\begin{eqnarray}
F_m\equiv 2 \quad (\bmod\, p)
\end{eqnarray}
for all $m>n$. In both cases we find $L=1$ and hence $p$ is anti-elite.
Let now $p=2^rh+1$ with $h$ odd be an anti-elite prime number with $L=1$. This means that $F_{r+1}\equiv F_{r+2}$ (mod $p$), i.e., there exists a quadratic residue $c$ modulo $p$ such that
\begin{eqnarray}
(c-1)^2+1\equiv c \quad (\bmod\, p).
\end{eqnarray}
This is equivalent to
\begin{eqnarray}
(c-1)(c-2)\equiv 0 \quad (\bmod\, p),
\end{eqnarray}
and so either $c\equiv 1$ or $c\equiv 2$ (mod $p$). The first case leads us to $2^{2^{r+1}}\equiv 0$ (mod $p$) which is impossible for all odd primes $p$. Hence, $c\equiv 2$ (mod $p$), resp. $F_{r+1}\equiv 2$ (mod $p$). Using relation (\ref{one}), we see that either $F_r\equiv 0$ (mod $p$), i.e. $p|F_r$, or $F_{r}\equiv 2$ (mod $p$). In the latter case we obtain -- again with formula (\ref{one}) -- either $F_{r-1}\equiv 0$ or $F_{r-1}\equiv 2$ (mod $p$) and so on. As we have $p>5$ there will hence be an index $n$ such that $31$.
\newtheorem{theo002}[theo001]{Theorem}
\begin{theo002}\label{t02}
Let $p=2^rh+1$ be an anti-elite prime number with a Fermat period of length $L>1$. Then there exists a quadratic residue $c$ modulo $p$ such that $F_{r}\equiv c+1 \,(\bmod\, p)$ and which is a solution of the Diophantine equation
\begin{eqnarray}
\sum_{\nu=0}^{2^L-2}c^\nu \equiv 0 \quad (\bmod\, p).
\end{eqnarray}
\end{theo002}
\begin{proof}
Let $p=2^rh+1$ be an anti-elite prime number. Write $F_{r}\equiv c+1$ (mod $p$), hence $c$ is a quadratic residue modulo $p$. Then $F_{r+L}\equiv c^{2^L}+1$ (mod $p$) and since $L$ is the length of the Fermat period of $p$, we obtain
\begin{eqnarray}
c^{2^L}\equiv c \quad (\bmod \, p),
\end{eqnarray}
which is equivalent to
\begin{eqnarray}
c(c-1)\sum_{\nu=0}^{2^L-2}c^\nu \equiv 0 \quad (\bmod\, p).
\end{eqnarray}
Notice that $c=0$ gives $F_{r}\equiv 1$ (mod $p$) which by (\ref{one}) leads to $F_{m}\equiv 1$ (mod $p$) for all $m>r$ contradicting $L>1$. The solution $c=1$ again only leads, as we have seen in the proof to Theorem \ref{t01}, to $L=1$. Hence, for $L>1$,
\begin{eqnarray}
\sum_{\nu=0}^{2^L-2}c^\nu \equiv 0 \quad (\bmod\, p).
\end{eqnarray}
This completes the proof.
\end{proof}
Let us now have a look at the special case $L=2$.
\newtheorem{coro002}[theo001]{Corollary}
\begin{coro002}\label{cor02}
Let $p=2^rh+1$ be a prime number. Then $p$ is anti-elite with $L=2$ if and only if $p$ fulfills the congruential equation $p\equiv 1\,(\bmod\, 12)$ and is a divisor of the number $N_r:=F_r(F_r-1)+1=2^{2^r}\left(2^{2^r}+1\right)+1$.
\end{coro002}
\begin{proof}
\
1) If $p$ is anti-elite with $L=2$ then there must exist a solution $c$ to the Diophantine equation
\begin{eqnarray}\label{elef}
c^2+c+1=kp,
\end{eqnarray}
where $k$ is an appropriate natural number. Notice that in Theorem \ref{t02} the residue $c$ is defined to be congruent to $F_r-1$. With (\ref{elef}), we hence get
\begin{eqnarray}
0\equiv c(c+1)+1\equiv F_r(F_r-1)+1 \quad (\bmod p),
\end{eqnarray}
i.e., $p$ is a divisor of $N_r$. Equation (\ref{elef}) has the two solutions
\begin{eqnarray}
c_1=\frac{-1+\sqrt{4kp-3}}{2}\quad\text{ and }\quad c_2=\frac{-1-\sqrt{4kp-3}}{2},
\end{eqnarray}
which are integer numbers only if $\sqrt{4kp-3}$ is a natural number, i.e., $4kp-3$ is a perfect square. Therefore there exists a solution to the quadratic congruential equation $x^2\equiv -3$ (mod 4p) and hence $\left(\frac{-3}{4p}\right)=1$. Now, we have
\begin{eqnarray}
\left(\frac{-3}{4p}\right)=\left(\frac{p}{3}\right)
\end{eqnarray}
using the fundamental properties of the Jacobi symbol and the Law of Quadratic Reciprocity. A simple computation shows that $\left(\frac{p}{3}\right)=1$ if and only if $p\equiv 1$ (mod 3). Hence, the even number $p-1$ is a multiple of 3. This means that $\omega:=\frac{p-1}{6}$ is a natural number and that there exists a cyclic subgroup $G$ modulo $p$ of order $6$ and index $\omega$ such that the two Fermat remainders of the period of $p$ are elements of $G$. So, there is a primitive root $a$ modulo $p$ such that the elements of $G$ have the form $a^{\omega\nu}$ with $\nu=0,1,\ldots,5$. Suppose that $\omega$ is odd, then $a^{\omega\nu}$ is a quadratic residue modulo $p$ only if $\nu$ is even. For $\nu=0$, we have $a^{\omega\nu}=1$ which cannot lead to $L=2$. So, the two Fermat remainders must be of the form $a^{2\omega}$, resp. $a^{4\omega}$. Furthermore, the relation
\begin{eqnarray}
\left(a^{2\omega}-1\right)^2+1\equiv a^{4\omega}\quad (\bmod \, p)
\end{eqnarray}
has to be fulfilled. But a simple transformation of this gives
\begin{eqnarray}
a^{2\omega}\equiv 1 \quad (\bmod p),
\end{eqnarray}
i.e., we again obtain a contradiction to the fact that $L=2$. Therefore, the index $\omega$ has to be an even number. This finally leads to $p\equiv 1$ (mod 12).
2) Let $p$ be a prime with $p\equiv 1$ (mod 12) and $p$ a divisor of $N_r$. There exists a quadratic residue $c$ modulo $p$ such that $F_{r}\equiv c+1$ (mod $p$). Hence, $N_r\equiv c^2+c+1\equiv 0$ (mod $p$). This implies that $F_{r}\equiv -c^2$ (mod $p$) and so, we get $\left(\frac{F_r}{p}\right)=\left(\frac{-1}{p}\right)=1$. Moreover, we obtain $F_{r+1}\equiv c^2+1\equiv -c$ (mod $p$), where $-c$ again is a quadratic residue modulo $p$. Finally, there is $F_{r+2}\equiv c^4+1\equiv (-c-1)^2+1\equiv c+1$ (mod $p$), i.e., $F_{r+2}\equiv F_r$ (mod $p$) and hence $p$ is anti-elite with $L=2$. This completes the proof.
\end{proof}
\newtheorem{cons002}[theo001]{Consequence}
\begin{cons002}\label{c02}
There are infinitely many anti-elite primes with $L=2$.
\end{cons002}
\begin{proof}
With relation (\ref{one}) we get
\begin{eqnarray*}
N_{r+1} & = & F_{r+1}^2-F_{r+1}+1\\
& = & \left((F_r-1)^2+1\right)^2-(F_r-1)^2\\
& = & (F_r^2-3F_r+3)(F_r^2-F_r+1)\\
& = & N_r(N_r-2(F_r-1)).
\end{eqnarray*}
Hence, for all natural numbers $m\leq M$ the number $N_m$ is a divisor of $N_M$. Especially, $N_1=21$ is a divisor of all $N_r$. It is an easy computation to check that
\begin{eqnarray}
N_r\equiv 9 \quad (\bmod\, 12)
\end{eqnarray}
and with this that
\begin{eqnarray}
\frac{N_r}{21}\equiv 1 \quad (\bmod\, 12),
\end{eqnarray}
resp.,
\begin{eqnarray}
\frac{N_{r+1}}{N_r}\equiv 1 \quad (\bmod\, 12),
\end{eqnarray}
hold for all natural numbers $r$. Notice that the two odd numbers $N_r$ and $\frac{N_{r+1}}{N_r}$ are relatively prime. Since any of their common divisors $d$ divides their difference, i.e., $d|2^{2^r+1}$, we see that $d$ is of the form $2^s$. This is possible only if $s=0$, i.e., $d=1$.
As we have shown in the proof to the previous Corollary, every prime factor $p>3$ of $N_r$ has a Fermat period of length $L=2$. Write $p=2^sh+1$ with $h$ odd. By the above mentioned Theorem of Aigner~\cite{aigner}, we know that if $2^jk$ with $0\leq j\leq s$ and $k$ a divisor of $h$ is the multiplicative order of $2$ modulo $p$, then $2^L=4\equiv 1$ (mod $k$). This implies that $k=3$. Because $2^j\cdot 3$ is a divisor of $\phi(p)=p-1$ we get $p\equiv 1$ (mod 3).
Suppose that $j\leq 1$. Then we get either $2^3=8\equiv 1$ (mod $p$), i.e., $p=7$ or $2^6=64\equiv 1$ (mod $p$), i.e., $p=3$ or $p=7$. But we already know that $(21,\frac{N_r}{21})=1$ and hence every prime factor $p>7$ of $N_r$ fulfills $p\equiv 1$ (mod 4).
Finally, every prime factor of $\frac{N_{r+1}}{N_r}$ has the form $p\equiv 1$ (mod 12) and it is relatively prime to all prime factors of the numbers $N_m$ with $m\leq r$. Corollary \ref{cor02} actually implies that every such prime factor is an anti-elite prime with $L=2$, such that there are infinitely many of these numbers.
\end{proof}
\paragraph{Remarks:} 1) Consequence \ref{c02} implies that for every $R>0$ there exists a natural number $r\geq R$ and an odd number $h>1$ such that $p=2^rh+1$ is anti-elite. Suppose that $r$ were bounded by $R$. Then all anti-elites $p$ with $L=2$ fulfill
\begin{eqnarray}
2^{2^{\lfloor R\rfloor}\cdot 3}\equiv 1 \quad (\bmod\, p).
\end{eqnarray}
This is possible only if $2^{2^{\lfloor R\rfloor}\cdot 3}>p$, i.e., for only finitely many $p$'s. The claim follows from this contradiction.
2) There is an alternate proof of Consequence \ref{c02} based on a well-known Theorem, first proved by A. S. Bang in 1886~\cite{bang}. It states that for any given integer $a>1$ and every natural number $n>6$ the number $a^n-1$ has a prime factor $p$ which does not divide $a^k-1$ for $1\leq k 2$ such that the number of anti-elites with period length $L$ is infinite?
\section*{Acknowledgement}
The author wishes to thank the friendly referee for his help to improve this paper and for pointing out an alternate proof of the main result.
\begin{thebibliography}{9}
\bibitem{aigner}
A. Aigner, \"Uber Primzahlen, nach denen (fast) alle Fermatzahlen quadratische Nichtreste sind, \textit{Monatsh. Math.} \textbf{101} (1986), 85--93.
\bibitem{bang}
A. S. Bang, Taltheoretiske undersogelser, \textit{Tidsskrift Math.} \textbf{5} (1886), 70--80, 730--137.
\bibitem{chaumont}
A. Chaumont and T. M\"uller, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Mueller/mueller12.html}{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, submitted.
\bibitem{golomb}
S. W. Golomb, Sets of primes with intermediate density, \textit{Math. Scand.} \textbf{3} (1955), 264--274.
\bibitem{kri}
M. K\v r\' i\v zek, F. Luca, and 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}
N. J. A. Sloane,
The Online Encyclopedia of Integer Sequences (OEIS),
electronically published at
\href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/\symbol{126}njas/sequences/}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11A15; Secondary 11A41.
\noindent \emph{Keywords: } anti-elite primes, elite primes, Fermat numbers.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence
\seqnum{A128852}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received June 28 2007;
revised version received September 18 2007.
Published in {\it Journal of Integer Sequences}, September 20 2007.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}