\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}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\lcm}{lcm}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf
On the Exponents of Non-Trivial Divisors of \\
\vskip .01in
Odd Numbers and a Generalization of  \\
\vskip .14in
Proth's Primality Theorem
}
\vskip 1cm
\large
Tom M\"uller \\
Institut f\"ur Cusanus-Forschung \\
University and Theological Faculty of Trier \\
Domfreihof 3 \\
54290 Trier \\
Germany \\
\href{mailto:mueller2887@t-online.de}{\tt mueller2887@t-online.de}\\
\end{center}

\begin{abstract}
We present a family of integer sequences characterizing the behavior of
the quotients $\sigma/s$ for a given odd natural number $H$,
where $N=H\cdot2^\sigma+1$ is a composite number and $h\cdot2^s+1$
($h\geq 1$ odd, $s,\sigma\in\mathbb{N}$) is a non-trivial divisor of
$N$. As an application we prove a generalization of the primality
theorem of Proth.
\end{abstract}

\section{Introduction}
For every odd natural number $N>1$ there exists an unique pair $(H,\sigma)$ with $H$ an odd natural number, $\sigma\in\mathbb{N}$ and $N=H\cdot2^\sigma+1$. In this parametric notation, we call $H$ the \textit{multiplier} of $N$ and $\sigma$ the \textit{exponent} of $N$. Here and subsequently, the notation $A\cdot2^\alpha+1$ always means that $A$ is the multiplier and $\alpha$ the exponent of the represented odd natural number. For a given natural number $N>1$ we let $\mathcal{D}(N)$ denote the set of the non-trivial divisors of $N$, i.e., the set of all natural numbers $d$ fulfilling $1<d<N$ and $d|N$. Obviously, $N$ is a prime number if and only if $\mathcal{D}(N)=\emptyset$.

The aim of this paper is to introduce and study a family of integer sequences characterizing the behavior of the quotient $\frac{\sigma}{s}$ for a given $H$, where $N=H\cdot2^\sigma+1$ is a composite number and $h\cdot2^s+1\in\mathcal{D}(N)$. These sequences can be used to give a generalization of the well-known primality theorem of Proth.

If the exponent $s$ is large compared to $\sigma$,
then there must exist a rather small real number $m>0$ with $m\geq \frac{\sigma}{s}$. All the values of $\sigma$ fulfilling this inequality for a given odd natural number $H$ are elements of the following set:
\begin{equation}\label{setdef}
S_m(H):=\left\{\sigma\in\mathbb{N}\,|\,\exists d=h\cdot2^s+1\in\mathcal{D}(H\cdot2^\sigma+1): m\geq\frac{\sigma}{s}\right\}.
\end{equation}
With this we define the integer sequence
\begin{equation*}
\sigma_m(H):=\sup\left(S_m(H)\right).
\end{equation*}
As usual, we adopt the conventions that $\sup(\emptyset)=0$ and $\sup(A)=\infty$ if $|A|=|\mathbb{N}|$. The aforementioned definitions immediately imply $S_k(H)\subset S_l(H)$ and hence $\sigma_k(H)\leq\sigma_l(H)$ if $k<l$.

\section{The $\sigma_m$-sequences}
\subsection{Diophantine equations}\label{prel1}
Definition (\ref{setdef}) leads to a general Diophantine equation, which allows to determine the elements of $S_m(H)$ for a given $m\geq 1$. Suppose $N=H\cdot2^\sigma+1=AB$ to be composite with two non-trivial divisors $A=h\cdot 2^r+1$ and $B=k\cdot 2^s+1$. Without loss of generality we can denote $A$ and $B$ such that $1\leq r\leq s$. It follows that
\begin{equation*}
AB= 2^r\left(2^shk+2^{s-r}k+h\right)+1 = 2^\sigma H + 1 = N.
\end{equation*}
This is equivalent to the Diophantine equation
\begin{equation}\label{gl1}
2^shk+2^{s-r}k+h=2^{\sigma-r} H.
\end{equation}
Note that $r\leq s\in\mathbb{N}$ and that $h$ and $k$ are odd natural numbers. To reflect the condition $m\geq\frac{\sigma}{s}$ of the definition we may include a supplementary parameter $n$ in order to write $\lfloor ms\rfloor-n=\sigma$. In general, $n$ can take any integer value between $0$ and $\lfloor ms\rfloor-1$. For practical purposes it is useful to demand for further restrictions, which render the computations more comfortable.

If $m=1$ then we get $r=\sigma<s$. Therefore, (\ref{gl1}) turns into
\begin{equation}\label{mequal1}
2^shk+2^{s-r}k+h=H.
\end{equation}
It is easy to see that for $H\in\{1,3\}$ equation (\ref{mequal1}) has no solution (under the abovementioned assumptions). Hence $\sigma_1(1)=\sigma_1(3)=0$. For $H>3$ the estimate $\sigma<s\leq\log_2(H)$ obviously holds. This gives $\sigma_1(H)\leq\lfloor\log_2(H)\rfloor-1$ for all $H\geq3$. In fact, this estimate is best possible in the sense that there are infinitely many values of $H$ for which we actually have $\sigma_1(H)=\lfloor\log_2(H)\rfloor-1$. We will establish this in subsection \ref{subssigma1}.

It is immediate that by explicitly giving a solution $(r,s,h,k,H)$ of (\ref{mequal1}), we get the lower bound $\sigma_1(H)\geq r$.

\begin{example}
Because $8\cdot\frac{10^n-1}{9}+2\cdot\frac{10^n-1}{9}+1=\frac{10^{n+1}-1}{9}$, we have $\sigma_1\left(\frac{10^{n+1}-1}{9}\right)\geq 2$ for all natural numbers $n$.
\end{example}
\begin{remark}
Since $\sigma_1(H)<\infty$ for every odd natural number $H$ it is obvious that $\sigma_m(H)<\infty$ for every $0<m<1$. Because of $S_m(H)\subset S_1(H)$, the value of $\sigma_m(H)$ can thus explicitly be calculated by examining the elements of $S_1(H)$.
\end{remark}
Note that for $m>1$ we already get $r=s<\sigma$ in the Diophantine equation (\ref{gl1}). Therefore, the Diophantine equation to consider concerning $\sigma_2(H)$ reads
\begin{equation}\label{mequal2}
2^shk+h+k=2^{\sigma-s}\cdot H
\end{equation}
with the supplementary condition $2s\geq\sigma$, i.e., $s\geq\sigma-s$. For computational reasons we will deal with another Diophantine equation in this context:
\begin{equation}\label{DEsigma2}
2^shk+h+k=2^{s-n}\cdot H
\end{equation}
with $h\leq k$ odd and $0\leq n<s$. Note that (\ref{DEsigma2}) follows from (\ref{mequal2}) by setting $2s=\sigma+n$. The solutions $(n,s,h,k,H)$ of (\ref{DEsigma2}) yield the elements $\sigma=2s-n\in S_2(H)\setminus S_1(H)$. Some simple but very useful results can be derived from this Diophantine equation. First, (\ref{DEsigma2}) implies $2^nhk<H$, showing that $\sigma_2(H)<\infty$ for every odd $H$. In subsection \ref{sigma2sec} we will give a best possible upper bound of the values of $\sigma_2(H)$. Again, by explicitly giving a solution $(n,s,h,k,H)$ of (\ref{DEsigma2}), we get the lower bound $\sigma_2(H)\geq 2s-n$.

\begin{example}
Since $4(8\cdot 10^w-1)+8\cdot 10^w=4(10^{w+1}-1)$, we see that $\sigma_2(10^{w+1}-1)\geq 4$ for all natural numbers $w$.
\end{example}
For $m=3$ there is also a condition for existence,
limiting the value of $n$ in the Diophantine equation
\begin{equation}\label{DEsigma3}
2^shk+h+k=2^{2s-n}\cdot H,
\end{equation}
where $h\leq k$ are odd natural numbers and $0\leq n<s$. Note that $(n,s,h,k,H)$ is a solution of equation (\ref{DEsigma3}) if and only if the corresponding $\sigma=3s-n$ is an element of $S_3(H)\setminus S_2(H)$.

Now consider such a solution $(n,s,h,k,H)$. By equation (\ref{DEsigma3}) we get $h+k\equiv 0$ (mod $2^s$), i.e., $h+k=2^s\cdot d$ for an appropriate natural number $d$. Moreover, there exists a natural number $a$ with $a+n=s$, i.e., $2s-n=s+a$. Then $hk=2^aH-d\leq2^aH-1$. This implies $h+k\leq hk+1\leq 2^aH\leq 2^sH$ and hence $2^s=\frac{h+k}{2^aH-hk}\leq2^aH$. Finally, he have $2^n=2^{s-a}\leq H$, yielding $n\leq\log_2(H)$.

\begin{remark}
This condition of existence already implies that $\sigma_m(H)<\infty$ for every odd $H$ and $m\in(2,3)$. To see this, suppose $\sigma\in S_m(H)\setminus S_2(H)\subset S_3(H)\setminus S_2(H)$ for a $m\in(2,3)$. This means that the corresponding $s$ leads to a solution in (\ref{DEsigma3}) and hence fulfils the inequality $s\leq\frac{\sigma+\log_2(H)}{3}$. Consequently, $\sigma$ satisfies $\frac{\sigma}{m}\leq \frac{\sigma+\log_2(H)}{3}$ which is equivalent to
\begin{equation}\label{letzte}
\sigma\leq\frac{m\log_2(H)}{3-m}.
\end{equation}
Since $\sigma_2(H)<\infty$, we can conclude with inequality (\ref{letzte}) that $\sigma_m(H)$ is finite as well.
\end{remark}
\subsection{Some elementary primality results}\label{prel2}
\begin{proposition}\label{propo101K}
Let $m$ be a natural number and $H\geq 1$ be an odd number such that $\sigma_m(H)=0$. Then $N:=H\cdot2^m+1$ is a prime number.
\end{proposition}
\begin{proof}
The number $N=H\cdot2^m+1$ is either prime or it has a non-trivial divisor of the form $h\cdot2^r+1$ with $r\geq 1=\frac{\sigma}{m}$. The latter case would imply $\sigma_m(H)\geq m>0$.
\end{proof}

\begin{corollary}\label{propo102K}
Let $H\geq 1$ be an odd number. Let $l$ be a nonnegative integer number and $m$ be a natural number with $\sigma_m(H)=l<m$. Then $N:=H\cdot2^\sigma+1$ is a prime number for every $\sigma\in[l+1,m]\cap\mathbb{N}$.
\end{corollary}
\begin{proof}
For $m=1$ this is exactly the claim of Proposition \ref{propo101K}. For $m>1$ we know that $r=s<\sigma$ if there are non-trivial divisors $A:=h\cdot 2^r+1$ and $B:=k\cdot 2^s+1$ of $N$ such that $AB=N$. But this leads to $m>s\geq1\geq\frac{\sigma}{m}$ and hence $\sigma_m(H)\geq \sigma>l$.
\end{proof}

\begin{corollary}\label{propo103K}
Let $H$ be an odd natural number and let $m\geq 1$ be a real number. If the natural number $\sigma\leq m$ is not an element of $S_m(H)$ then $N=H\cdot 2^\sigma+1$ is a prime number.
\end{corollary}
\begin{proof}
Let $N=H\cdot2^\sigma+1=AB$ be a composite number with $\sigma\leq m$. As usual, write $A=h\cdot2^r+1$ and $B=k\cdot2^s+1$ with $r\leq s$. Now suppose that $\sigma$ is not an element of $S_m(H)$. Then we have $s< \frac{\sigma}{m}\leq 1$, contradicting the condition $1\leq s$.
\end{proof}

\subsection{Special values of $\sigma_1$}\label{subssigma1}
\begin{theorem}\label{lemma101K}
Let $l$ and $m\geq l+1$ be natural numbers. Then $\sigma_1(2^m+2^l+1)\geq m-l$.
\end{theorem}
\begin{proof}
Under the conditions of the theorem, $(r,s,h,k,H)=(m-l,m,1,1,2^m+2^l+1)$ is a solution of (\ref{mequal1}).
\end{proof}

\begin{theorem}\label{lemma102K}
Let $m\geq2$ be a natural number. Then $\sigma_1(2^m+3)=m-1$.
\end{theorem}
\begin{proof}
For every $H>1$ we know that $\sigma_1(H)\leq\lfloor\log_2(H)\rfloor-1$. Therefore, $\sigma_1(2^m+3)\leq m-1$ for all $m\geq2$. The claim follows with Theorem \ref{lemma101K}.
\end{proof}

On the one hand, Theorem \ref{lemma102K} shows that for every $H=2^m+3$ ($m\geq2$) the best possible value $\sigma_1(H)=\lfloor \log_2(H)\rfloor-1$ is actually reached. On the other hand, we can conclude that the arithmetical function $\sigma_1: \mathbb{N}\setminus2\mathbb{N}\rightarrow\mathbb{N}_0$ is surjective.

\begin{theorem}\label{lemma103K}
Let $m\geq3$ be a natural number. Then $\sigma_1(2^m+5)=m-2$.
\end{theorem}
\begin{proof}
Theorem \ref{lemma101K} gives $\sigma_1(2^m+5)\geq m-2$ for all $m\geq 3$. Moreover, $\sigma_1(2^m+5)\leq\lfloor\log_2(H)\rfloor-1=m-1$ for all $m\geq 3$. Suppose that there were a solution of (\ref{mequal1}) yielding $\sigma=m-1$. This solution would have to be of the form $2^mhk+2k+h=2^m+5$, since $s\leq\log_2(H)$. But for $h=k=1$ we have $2^m+2+1<2^m+5$, whereas for $\max\{h,k\}>1$ there is $2^m+5<2^mhk+2k+h$. Thus, such a solution does not exist.
\end{proof}
\begin{remark}
The sequence $(a(n))_{n\geq0}$ with $a(n)=\sigma_1(2n+1)$ is sequence \seqnum{A272894} of the OEIS.
\end{remark}
\subsection{Special values of $\sigma_2$}\label{sigma2sec}
\begin{theorem}\label{lemma001K}
Let $m$ be a natural number and let $H$ be an odd natural number with $H<2^m$. Then $\sigma_2(H)\leq 2m-1$.
\end{theorem}
\begin{proof}
We already know that $\sigma_1(H)\leq\log_2(H)<m$, so we do not have to consider the solutions of (\ref{mequal1}) here. Given the Diophantine equation (\ref{DEsigma2}), we see that $h+k\equiv 0$ (mod $2^{s-n}$), i.e., there is a natural number $d$ with $h+k=d\cdot 2^{s-n}$. This implies $2^nhk=H-d\leq 2^m-2$ or
\begin{equation}\label{hkabsch}
hk\leq \frac{2^m-2}{2^n}.
\end{equation}

First, if $n=0$ then (\ref{hkabsch}) gives
$$h+k\leq hk+1\leq 2^m-1<2^m.$$
Consequently, a transformation of the Diophantine equation (\ref{DEsigma2}) leads to
$$2^s=\frac{h+k}{H-hk}<2^m,$$
since $H-hk$ is a natural number. So, here we have $s<m$, i.e., $s\leq m-1$ and hence $\sigma\leq 2m-2$.

Secondly, for $n\geq 1$, again with (\ref{hkabsch}), we get
$$h+k\leq hk+1\leq 2^{m-n}+1-\frac{1}{2^{n-1}}.$$
This means that the even natural number $h+k$ always fulfils $h+k\leq 2^{m-n}$. In the present case, the Diophantine equation (\ref{DEsigma2}) can be changed into
$$2^{s-n}=\frac{h+k}{H-2^nhk}\leq 2^{m-n}$$
with a natural denominator $H-2^nhk$, giving the estimations $s\leq m$ and $\sigma\leq 2m-n$. The maximal value of the latter expression obviously is $2m-1$. Therefore, $\sigma_2(H)\leq 2m-1$ for every $H<2^m$.
\end{proof}

Moreover, the arguments $H$ leading to maximal values of $\sigma_2(H)$ can be specified.
\begin{theorem}\label{lemma005K}
Let $m\geq 2$ be a natural number and let $H$ be an odd natural number with $H<2^m$. Then $\sigma_2(H)=2m-1$ if and only if $H=2^m-1$.
\end{theorem}
\begin{proof}
\ \\
(1) If $H=2^m-1$ with $m\geq 2$ then the Diophantine equation (\ref{DEsigma2}) has the solution $(n,s,h,k)=(1,m,1,2^{m-1}-1)$ and consequently $\sigma_2(H)=2m-1$.

\medskip

\noindent (2) Suppose that $\sigma_2(H)=2m-1$ for a $H<2^m$. The Diophantine equation $h+k=hk+1$ (under the assumption that $1\leq h\leq k$) implies $h=1$. So, if $3\leq h\leq k$, then we have $h+k<hk$. Note that $h+k=hk$ is impossible for every odd $k$. Applying (\ref{hkabsch}) we can assert that
$$h+k<hk\leq\frac{2^m-2}{2^n}<2^{m-n}$$
for $3\leq h\leq k$ and $H<2^m$. Hence $2^{s-n}<2^{m-n}$. This leads to $s\leq m-1$ and $\sigma\leq 2m-2-n\leq 2m-2$.

It follows that $\sigma=2m-1$ requires $h=1$, $n=1$ and $s=m$. Then (\ref{DEsigma2}) can be rewritten as
\begin{equation*}
2^mk+k+1=2^{m-1}H,
\end{equation*}
or
\begin{equation}\label{kado}
k+1=2^{m-1}(H-2k).
\end{equation}
As seen above, we have $k+1=k+h\leq 2^{m-n}=2^{m-1}$ and hence $H-2k=1$, or 
\begin{equation}\label{cadeau}
k=\frac{H-1}{2}.
\end{equation}
Substituting (\ref{cadeau}) in (\ref{kado}) yields $H=2^m-1$.
\end{proof}

\begin{remark}
Combining the Theorems \ref{lemma001K} and \ref{lemma005K} yields the inequality $\sigma_2(H)\leq 2\log_2(H)$ for every odd natural number $H$.
\end{remark}
Some other subsequences can be given in parametric form.
\begin{theorem}\label{lemma006K}
Let $m\geq 3$ be a natural number and let $H$ be an odd natural number with $H<2^m$. Then $\sigma_2(H)=2m-2$ if and only if $H=2^m-3$.
\end{theorem}
\begin{proof}
\ \\
\noindent (1) For $H=2^m-3$ with $m\geq 3$ there is the solution
$$(n,s,h,k)=(2,m,1,2^{m-2}-1)$$
to the Diophantine equation (\ref{DEsigma2}), i.e., $\sigma=2m-2$. Theorem \ref{lemma005K} states that $\sigma_2(2^m-3)\not=2m-1$, which is why $\sigma_2(2^m-3)=2m-2$.

\medskip

\noindent (2) Suppose that for a $H<2^m$ we have $\sigma_2(H)=2m-2$. The only pairs $(n,s)$ leading to $\sigma=2s-n=2m-2$ are $(0,m-1)$ or $(2,m)$. Moreover, we know that $3\leq h\leq k$ implies $s<m$. Therefore, the second pair requires $h=1$ and transforms (\ref{DEsigma2}) into $2^mk+k+1=2^{m-2}H$ or
\begin{equation}\label{sub1}
k+1=2^{m-2}(H-4k).
\end{equation}
Because $k+1\leq 2^{m-2}$, we get $H-4k=1$, i.e., $k=\frac{H-1}{4}$. Substituting $k$ in (\ref{sub1}) yields $H=2^{m}-3$.

Let us now turn our attention to the pair $(0,m-1)$. Suppose that there is a solution to the Diophantine equation $2^{m-1}hk+h+k=2^{m-1}H$ with $H<2^m$. A simple transformation gives $h+k=2^{m-1}(H-hk)$, yielding $H-hk=2$ since $h+k\leq2^m$ and $H-hk$ even. So, $h=2^m-k$ and $h=\frac{H-2}{k}$. Combining these two equalities gives $k^2-2^mk+H-2=0$, or
$$H=-k^2+2^mk+2.$$
Note that the inequality $-k^2+2^mk<2^m-2$ is fulfilled for no $1\leq k<2^m$. This can be verified, e.g., by basic analytic considerations of the polynomial function $f(x)=-x^2+2^mx-2^m$. Consequently, we obtain $H>2^m$. This contradiction proves the theorem.
\end{proof}
\begin{theorem}\label{lemma007K}
Let $m>3$ be a natural number. Then $\sigma_2(2^m+1)=2m-2$.
\end{theorem}
\begin{proof}
Note that for all $m>3$ there is $\sigma_1(2^m+1)\leq\lfloor\log_2(2^m+1)\rfloor-1=m-1\leq2m-2$. Consider the equality $2^{m-1}(2^m-1)+2^m=2^{m-1}(2^m+1)$ showing that $(n,s,h,k)=(0,m-1,1,2^m-1)$ is a solution of the Diophantine equation (\ref{DEsigma2}). Therefore, we have $\sigma_2(2^m+1)\geq2m-2>\sigma_1(2^m+1)$. According to the Theorems \ref{lemma001K}, \ref{lemma005K} and \ref{lemma006K}, the only larger value that $\sigma_2(2^m+1)$ could equal to for $m\geq 3$ is $2m-1$. The latter value requires $(n,s)\in\{(1,m),(3,m+1)\}$. The first of these pairs gives $2^mhk+h+k=2^{m-1}(2^m+1)$ or
$$h+k=2^{m-1}(2^m+1-2hk)\leq2^m.$$
Since $2^m+1-2hk$ is odd, this implies $2^m+1-2hk=1$ which is impossible for odd $h$ and $k$ when $m>3$. The second pair yields $2^{m+1}hk+h+k=2^{m-2}(2^m+1)$ or
$$h+k=2^{m-2}(2^m+1-8hk)\leq2^{m-2}.$$
This gives $2^m+1-8hk=1$, an equality that also cannot hold for odd $h$ and $k$ when $m>3$. Hence, $\sigma_2(2^m+1)=2m-2$ for all $m>3$.
\end{proof}
\begin{theorem}\label{lemma008K}
Let $m\geq 3$ be a natural number. Then $\sigma_2(2^m+3)=2m-4$.
\end{theorem}
\begin{proof}
Note that for all $m\geq 3$ there is $\sigma_1(2^m+3)\leq\lfloor\log_2(2^m+3)\rfloor-1=m-1\leq2m-4$. Consider the equality $2^{m-2}(2^m-1)+2^m=2^{m-2}(2^m+3)$. Thus $(n,s,h,k)=(0,m-2,1,2^m-1)$ is a solution of the Diophantine equation (\ref{DEsigma2}) for all $m\geq 3$ and hence $\sigma_2(2^m+3)\geq 2m-4\geq\sigma_1(2^m+3)$. Because $2^m+3<2^{m+1}-3$ for all $m\geq 3$, we know by the Theorems \ref{lemma001K}, \ref{lemma005K} and \ref{lemma006K} that $\sigma_2(2^m+3)<2(m+1)-2=2m$. Therefore, other potential values for $\sigma_2(2^m+3)$ are $2m-3, 2m-2$ or $2m-1$.

To obtain $\sigma=2m-3$ we need $(n,s)\in\{(1,m-1),(3,m),(5,m+1)\}$.

The first pair gives $2^{m-1}hk+h+k=2^{m-2}(2^m+3)$ or
\begin{equation}\label{sub2}
h+k=2^{m-2}(2^m+3-2hk).
\end{equation}
Since $h+k\leq2^{m}$, the odd natural number $2^m+3-2hk$ can take the values $1$ or $3$.

\medskip

\noindent (a) $2^m+3-2hk=1$ is equivalent to $h=\frac{2^{m-1}+1}{k}$. Substituting $h$ in (\ref{sub2}) gives $k^2-2^{m-2}k+2^{m-1}+1=0$. The latter quadratic equation has integer solutions $k$ only if $\Delta=2^{2m-2}-4(2^{m-1}+1)=4(2^{2m-4}-2^{m-1}-1)$ is a perfect square. It is easy to see that $\Delta$ is a perfect square if and only if $\frac{\Delta}{4}$ is one as well. But for $m\geq 3$ we have $\frac{\Delta}{4}\equiv 3$ (mod $4$), which is impossible for a perfect square.

\medskip

\noindent (b) $2^m+3-2hk=3$ is equivalent to $h=\frac{2^{m-1}}{k}$ which is impossible for odd $h$ and $k$.

\medskip

The pair $(3,m)$ yields $2^{m}hk+h+k=2^{m-3}(2^m+3)$ or
$$h+k=2^{m-3}(2^m+3-8hk).$$
Here, we have $h+k\leq2^{m-2}$ and so, the odd natural number $2^m+3-8hk$ can only take the value $1$. This gives $h=\frac{2^{m-1}+1}{4k}$ which is impossible.

With the pair $(5,m+1)$ we get $2^{m+1}hk+h+k=2^{m-4}(2^m+3)$ or
$$h+k=2^{m-4}(2^m+3-32hk).$$
Here, we have $h+k\leq 2^{m-4}$ and hence $2^m+3-32hk=1$ or $h=\frac{2^{m-1}+1}{16k}$ which again is impossible. We can conclude that $\sigma_2(2^m+3)\not=2m-3$.

The case $\sigma=2m-2$ requires $(n,s)\in\{(0,m-1),(2,m),(4,m+1)\}$, while for $\sigma=2m-1$ there ought to be $(n,s)\in\{(1,m),(3,m+1)\}$. In total analogy to the case $\sigma=2m-3$, one can establish that none of these five pairs leads to a solution of the Diophantine equation (\ref{DEsigma2}). The details of these computations are left to the reader. Consequently, $\sigma_2(2^m+3)=2m-4$ for all $m\geq 3$.
\end{proof}

\begin{remark}
\ \\
\noindent (1) We know that $\sigma_2(1)=0$. Moreover, the Theorems \ref{lemma008K} and \ref{lemma005K} state that for every natural number $N\geq 2$ there exists an odd number $H$ with $\sigma_2(H)=N$. A question arising from these observations is, whether the sequence $\sigma_2$ is surjective on $\mathbb{N}_0$? The answer is ``yes'', since a straightforward computation yields $\sigma_2(27)=1$.

\medskip

\noindent (2) The sequence $(a(n))_{n\geq0}$ with $a(n)=\sigma_2(2n+1)$ is sequence \seqnum{A272895} of the OEIS.
\end{remark}

\subsection{Some further observations about $\sigma_3$}
The Diophantine equation (\ref{DEsigma3}) is equivalent to
\begin{equation}\label{parameterDE3}
h+k=2^s(2^{s-n}H-hk).
\end{equation}
From the observations made at the end of subsection \ref{prel1} we know that $h+k\leq 2^s\cdot H$. So, there is an odd natural number $\alpha\leq H$ with $2^{s-n}H-hk=\alpha$, i.e., $h=\frac{2^{s-n}H-\alpha}{k}$. Substituting $h$ in (\ref{parameterDE3}) gives
\begin{equation}\label{DE3allg}
k^2-2^s\alpha k+2^{s-n}H-\alpha=0.
\end{equation}
The latter quadratic equation in the variable $k$ is solvable in integers if and only if the number $\tau:=2^{2s-2}\alpha^2+\alpha-2^{s-n}H$ is a perfect square.

We study two different cases. First, if $\alpha\equiv 3$ (mod $4$) then we have to consider the following subcases. If $s-n=1$ then $\tau$ has the form $2^{2n}\alpha^2+\alpha-2H$. So, for $n=0$ we get $\tau=\alpha^2+\alpha-2H\equiv 2$ (mod $4$), which cannot be a perfect square. In the case $n\geq 1$ this yields $\tau\equiv 1$ (mod $4$) and hence a potential perfect square leading to a solution of (\ref{DE3allg}) of the form $k=2^n\alpha\pm\sqrt{2^n\alpha^2+\alpha-2H}$. The corresponding value of $\sigma$ would be $\sigma=3(n+1)-n=2n+3$. Note, that the condition $1\leq n\leq\log_2(H)$ has to be fulfilled, which is why only a finite number of solutions of the latter form can exist. If $s-n\geq 2$ then $\tau\equiv 3$ (mod $4$) and hence $\tau$ never is a perfect square.

Secondly, let $\alpha\equiv 1$ (mod $4$). Again consider the case $s-n=1$, i.e., $\tau=2^{2n}\alpha^2+\alpha-2H$. For $n=0$ we get $\tau\equiv 0$ (mod $4$) and therefore the potential solution $k=\alpha\pm\sqrt{\alpha^2+\alpha-2H}$ with a corresponding $\sigma=3$. If $n\geq 1$ then $\tau\equiv 3$ (mod $4$) cannot be a perfect square. The case $s-n\geq 2$ always gives $\tau\equiv 1$ (mod $p$) and hence potential solutions of the form $k=2^{s-1}\alpha\pm\sqrt{2^{2s-2}\alpha^2+\alpha-2^{s-n}H}$ with corresponding $\sigma=3s-n$.

Note that the latter subcase is the only one that could possibly lead to an infinity of solutions. More precisely, we can have $\sigma_3(H)=\infty$ only if $\tau=2^{2s-2}\alpha^2+\alpha-2^{s-n}H$ is a perfect square for an infinity of tuples $(s,n,\alpha)$ fulfilling $0\leq n<s-1$, $n\leq\log_2(H)$ and $1\leq\alpha\leq H$ with $\alpha\equiv 1$ (mod $4$).

\begin{proposition}\label{propoKK007K}
Let $H$ be an odd natural number. Then

\noindent 1) $\sigma=3\in S_3(H)\setminus S_2(H)$ if $k=\alpha\pm\sqrt{\alpha^2+\alpha-2H}$ and $h=\frac{2^{s-n}H-\alpha}{k}$ are odd natural numbers for a given $\alpha\equiv 1$ $(\bmod\, 4)$ with $\alpha\leq H$.

\noindent 2) $\sigma=3s-n\in S_3(H)\setminus S_2(H)$ if $k=2^{s-1}\alpha\pm\sqrt{2^{2s-2}\alpha^2+\alpha-2^{s-n}H}$ and $h=\frac{2^{s-n}H-\alpha}{k}$ are odd natural numbers for $0\leq n<s-1$, $n\leq\log_2(H)$ and $1\leq\alpha\leq H$ with $\alpha\equiv 1$ $(\bmod\, 4)$.

\noindent 3) $\sigma=2n+3\in S_3(H)\setminus S_2(H)$ if $k=2^n\alpha\pm\sqrt{2^n\alpha^2+\alpha-2H}$ and $h=\frac{2^{s-n}H-\alpha}{k}$ are odd natural numbers for $1\leq n\leq \log_2(H)$ and $\alpha\leq H$ with $\alpha\equiv 3$ $(\bmod\, 4)$.

\noindent These three cases give all possible elements of the set $S_3(H)\setminus S_2(H)$.
\end{proposition}

\begin{example}
\ \\
\noindent (1) For a given odd natural number $t$ the tuples $(s,0,t^2)$ yield the perfect squares $2^{2s-2}t^4+t^2-2^st^3=(2^{s-1}t^2-t)^2$ for all $s\in\mathbb{N}$, leading to $k=2^st^2-t$ and $h=t$. This means that $\sigma_3(t^3)=\infty$ for every odd natural number $t$.

\noindent (2) It is easy to verify that the expressions $2^{2s-2}+1-2^{s-n}\cdot 3$ are never perfect squares for $n\in\{0,1\}$ and $s\geq n+2$. Thus, we obtain $\sigma_3(3)<\infty$. A straightforward computation actually yields $\sigma_3(3)=\sigma_2(3)=3$.
\end{example}

\section{Primality testing and generalized Fermat numbers}
In 1877, P\'epin~\cite{pepin} showed that for $n>1$ the Fermat number $F_n=2^{2^n}+1$ is prime if and only if $5^\frac{F_n-1}{2}\equiv -1$ (mod $F_n$). The so-called P\'epin test has since been a popular method to check Fermat numbers for primality. A structural equivalence of P\'epin's test for Fermat numbers and the Lucas-Lehmer test for Mersenne numbers has been brought to light recently~\cite{jaroma}.

Some further results were inspired by P\'epin's theorem. First, Proth~\cite{proth} found the following generalization: Let $N=H\cdot 2^\sigma+1$ be an odd number with $2^\sigma>H$. Let $b$ be a quadratic nonresidue modulo $N$. Then $N$ is a prime number if and only if $b^\frac{N-1}{2}\equiv -1$ (mod $N$). So called Proth primes, i.e., numbers that can be shown being prime using Proth's theorem, play an important role in finding factors of Fermat numbers.

Another question, arising from an observation by Lucas~\cite[p.\ 313]{lucas2}, was brought up by Aigner~\cite{aigner} in 1986: Are there other prime numbers suitable to be used as bases in P\'epin's test? Aigner identified the basic property of any suitable prime number $p$ to be that almost all Fermat numbers are quadratic nonresidues modulo $p$. He found 14 such primes less than $35\cdot 10^6$ and, because of their rareness, called them \textit{elite} prime numbers. In recent years, elite primes have been the subject of a number of research papers~\cite{chaumont1,chaumont2,krizek1,krizek2,muller1,muller2,muller3,witno1,witno2}.

In this context, Reinhart and the author~\cite{muller2,muller4} studied some fundamental properties of the behavior of the so called Fermat periods of natural numbers. For a natural number $b$ consider the generalized Fermat numbers $F_{b,n}=b^{2^n}+1$. Because of the recurrence relation $F_{b,n+1}=(F_{b,n}-1)^2+1$ it is obvious that the congruence $F_{b,n}$ (mod $N$) becomes periodic for every natural number $N$, i.e., there exist minimal nonnegative integer numbers $s$ and $L\geq 1$ such that $F_{b,s}\equiv F_{b,s+Lk}$ (mod $N$) for all natural numbers $k$. We call the parameter $s=:s_b(N)$ the \textit{start index} and $L=:L_b(N)$ the \textit{period length} of the $b$-Fermat period of $N$. Some applications of generalized Fermat numbers have been studied~\cite{caldwell, cosgrave, gulliver, kurlberg}. For a survey on Fermat numbers we refer the reader to the book
of K{\v r}\'{\i}{\v z}ek,
Luca, and Somer~\cite{krizek0}. Some generalizations of Proth's theorem dealing with other parametric forms of $N=Ka^n+b$ have been discussed by several authors~\cite{berriz,grau,guthmann}. In this section, we give another generalization of Proth's primality theorem lowering the requirements that the base $b$ has to fulfil.
\begin{theorem}\label{hauptsatz001K}
Let $H$ be an odd natural number and let $m\geq 1$ be a real number such that $\sigma_m(H)<\infty$. Let $N=H\cdot 2^\sigma+1$ be an odd natural number with $\sigma>\sigma_m(H)$. Then $N$ is a prime number if and only if there are two natural numbers $b$ and $k$ with $\gcd(N,b)=1$, $k\geq \frac{\sigma}{m}$ and $b^{2^{k-1}H}\equiv -1\, (\bmod\, N)$.
\end{theorem}
\begin{remark}
\ \\
\noindent (1) Taking into account the inequality $\sigma_1(H)\leq\log_2(H)$, Proth's theorem follows from Theorem \ref{hauptsatz001K} when we use $m=1$.

\medskip

\noindent (2) In many cases, the condition $\sigma>\sigma_m(H)$ is actually weaker than that demanded by Proth. E.g., $\sigma_1(3)=0$, $\sigma_2(165)=0$, $\sigma_2(27)=\sigma_2(45)=\sigma_2(267)=1$, $\sigma_2(H)=2$ for $H\in\{11, 51, 85, 195, 201, 231, \ldots\}$, $\sigma_2(H)=3$ for $H\in\{21,37,55,87,93,123,153,$ $181,243,245,\ldots\}$, etc.

\medskip

\noindent (3) Proth's theorem needs the base $b$ to be a quadratic nonresidue modulo $N$. In our result this requirement falls aside for $m>1$. E.g., because of $\sigma_2(1)=0$, the first four Fermat Numbers $F_n:=2^{2^n}+1$ ($n\in\{0,1,2,3\}$) can be proved being prime numbers using Theorem \ref{hauptsatz001K} with $b=2$, $k:=n+1\geq2^{n-1}$ and $2^{2^{k-1}}\equiv -1 $ (mod $F_n$). Unfortunately, for all $n\geq 4$ the base $b=2$ is not suitable anymore and $b=3$, i.e., P\'epin's Test, has to be applied for larger Fermat Numbers.
\end{remark}
The proof of Theorem \ref{hauptsatz001K} is based on elementary properties of $b$-Fermat periods and thus points out another application of generalized Fermat numbers.

\subsection{Fermat periods}
Using the parametric form $N=H\cdot 2^\sigma+1$ allows a characterization of the start index and the length of the Fermat periods of $N$~\cite{muller4}.
\begin{theorem}\label{satz001K}
Let $N=H\cdot2^\sigma+1$ and $b$ be natural numbers with $\gcd(N,b)=1$. We let $t\cdot2^s$ ($t$ odd) denote the multiplicative order of $b$ modulo $N$. Then we have $s_b(N)=s$ and $L_b(N)=\ord_t(2)$. If $N$ is a prime number, then $s\leq\sigma$ and $t$ divides $H$.
\end{theorem}
A result linking the period length of a composite $N$ to the period lengths of coprime factors is also known~\cite{muller4}.
\begin{theorem}
Let $A$ and $B$ be two coprime natural numbers and $b\in\mathbb{N}$. Then $L_b(AB)=\lcm(L_b(A),L_b(B))$.
\end{theorem}
A similar result can be shown for the start indices of composite numbers.
\begin{proposition}\label{folg1K}
Let $A$, $B$ and $b$ be natural numbers with $\gcd(A,B)=\gcd(AB,b)=1$. Then $s_b(AB)=\max\{s_b(A),s_b(B)\}$.
\end{proposition}
\begin{proof}
It is well-known that for natural numbers $A$, $B$ and $b$ with $\gcd(A,B)=\gcd(AB,b)=1$ we have $\ord_{AB}(b)=\lcm(\ord_A(b),\ord_B(b))$. With Theorem \ref{satz001K} this implies $s_b(AB)=\max\{s_b(A),s_b(B)\}$.
\end{proof}

The following proposition settles the problem of the start indices of non-squarefree numbers.
\begin{proposition}\label{folg2K}
Let $p$ be an odd prime number. Let $m$ and $b$ be natural numbers with $\gcd(p,b)=1$. Then $s_b(p^m)=s_b(p)$.
\end{proposition}
\begin{proof}
We let $\alpha$ denote the multiplicative order of $b$ modulo $p$, i.e., $b^\alpha=pk+1$ for a suitable $k\in\mathbb{Z}$. This leads to
\begin{align*}
b^{\alpha p^{m-1}} & = (pk+1)^{p^{m-1}}\\
& = \sum_{\nu=0}^{p^{m-1}}\binom{p^{m-1}}{\nu}p^\nu k^\nu\\
& \equiv 1 \quad (\bmod \,p^m).
\end{align*}
It follows that the multiplicative order of $b$ modulo $p^m$ is a divisor of $\alpha p^{m-1}$. Now suppose that there is a $\beta<\alpha$ fulfilling $b^{\beta p^{m-1}}\equiv 1$ (mod $p^m$). Then Fermat's little theorem implies $b^\beta\equiv 1$ (mod $p$), contradicting the fact that $\alpha$ is the multiplicative order of $b$ modulo $p$.

So, the multiplicative order of $b$ modulo $p^m$ has to be of the form $\alpha p^d$ with $d\in\{0,1,\ldots,m-1\}$. By writing $p=h\cdot2^r+1$, Theorem \ref{satz001K} states that $\alpha=2^st$ with $s\leq r$, $t$ a divisor of $h$ and $s_b(p)=s$. Again with Theorem \ref{satz001K}, this time applied to $p^m$, we obtain the start index $s_b(p^m)=s$ since $\ord_{p^m}(b)=2^stp^d$ and $tp^d$ is odd.
\end{proof}

\begin{corollary}\label{consK}
Let $N=\prod_{\nu=1}^n p_\nu^{\alpha_\nu}$ be the canonical prime factorization of an odd natural number $N$. Then $s_b(N)=\max_{1\leq\nu\leq n}\{s_b(p_\nu)\}$ for every base $b\in\mathbb{N}$ with $\gcd(N,b)=1$.
\end{corollary}
\begin{proof}
By induction over the number of prime factors, Proposition \ref{folg1K} can be generalized to $s_b(N)=\max_{1\leq k\leq n}\{s_b(p_k^{\alpha_k})\}$. With Proposition \ref{folg2K} we then get $s_b(N)=\max_{1\leq k\leq n}\{s_b(p_k)\}$.
\end{proof}

\begin{remark}
All the results formulated so far for Fermat numbers remain correct if we consider power sequences instead. So, for practical use, it does not matter whether we investigate the congruential behavior of the numbers $F_{b,n}$ or that of the numbers $b^{2^n}$.
\end{remark}

\subsection{A primality theorem using Fermat periods}
\begin{theorem}\label{satz002K}
Let $H$ be an odd natural number and let $m\geq 1$ be a real number such that $\sigma_m(H)<\infty$. Let $N=H\cdot2^\sigma+1$ be an odd natural number with $\sigma> \sigma_m(H)$. Then $N$ is a prime number if and only if there is a natural number $b$ with $\gcd(N,b)=1$ and $s_b(N)\geq\frac{\sigma}{m}$.
\end{theorem}
\begin{proof}
\ \\
\noindent (1) Suppose $N=H\cdot2^\sigma+1$ to be a prime number. Then there exists a primitive root $b$ modulo $N$, i.e., $\gcd(N,b)=1$ and $\ord_N(b)=2^\sigma\cdot H$. With Theorem \ref{satz001K}, this implies $s_b(N)=\sigma\geq\frac{\sigma}{m}$.

\medskip

\noindent (2) Let $b$ be a natural number with $\gcd(N,b)=1$ and $s_b(N)\geq\frac{\sigma}{m}$. Suppose that $N=H\cdot2^\sigma+1=AB$ is a composite number with the two factors $A=h\cdot 2^r+1$ and $B=k\cdot 2^s+1$. Note that by definition there is $1<A,B$. Therefore, the numbers $A$ and $B$ represent every possible combination of two nontrivial divisors of $N$ that multiply to $N$.

Since $\sigma>\sigma_m(H)$, we know that $r=s<\frac{\sigma}{m}$. It follows that every prime factor $p=q\cdot 2^w+1$ of $N$ must fulfil $w<\frac{\sigma}{m}$. Corollary \ref{consK} then implies $s_b(N)<\frac{\sigma}{m}$ for every base $b$ with $\gcd(N,b)=1$. This contradiction proves the theorem.
\end{proof}

\subsection{Proof of Theorem \ref{hauptsatz001K}}

\noindent(1) Let $N$ be a prime number. Then there is a primitive root $b$ modulo $N$ fulfilling $\gcd(N,b)=1$ and, by Euler's criterion, $b^{2^{\sigma-1}H}\equiv -1$ (mod $N$).

\medskip

\noindent(2) Let $b$ and $k$ be natural numbers with $\gcd(N,b)=1$, $k\geq \frac{\sigma}{m}$ and 
$$b^{2^{k-1}H}\equiv -1\, (\bmod\, N).$$
Therefore, $2^kH$ is a multiple of the multiplicative order of $b$ modulo $N$, while $2^{k-1}H$ is not. Hence, there must be a divisor $d$ of $H$ such that $\ord_N(b)=2^kd$. Theorem \ref{satz001K} now gives $s_b(N)=k\geq\frac{\sigma}{m}$. Since $\sigma>\sigma_m(H)$, we can apply Theorem \ref{satz002K} and we immediately obtain the primality of $N$.\hfill $\square$

\section{Discussion and open problems} 

\noindent (1) Are there more elegant criteria than those of Proposition \ref{propoKK007K} to decide whether $\sigma_3(H)<\infty$? Are the multipliers $H=t^3$ the only values giving $\sigma_3(H)=\infty$?

\medskip

\noindent (2) Are there conditions of existence for values $m>3$ allowing to evaluate $\sigma_m(H)$?

\medskip

\noindent (3) Another open problem is the question how to efficiently find a suitable base $b$ in order to use Theorem \ref{hauptsatz001K} for primality testing. The following heuristic argument suggests that it might suffice to try $b=2$ for $m\geq 2$, $H\geq 3$ with $\sigma_m(H)<\infty$ and large $\sigma$. We know that for every prime number $p=H\cdot 2^\sigma+1$ that is not a divisor of $2^H-1$, there exists a generalized Fermat number of the form $(2^H)^{2^{k-1}}+1$ being a multiple of $p$. In such a case, the difference $\sigma-k:=t$ indicates that $2^H$ is a $2^t$-power residue but not a $2^{t+1}$-power residue modulo $p$~\cite{bjorn}. Now suppose that $k<\frac{\sigma}{m}$. This would imply $t>\frac{(m-1)\sigma}{m}$ and thus $2^H$ would have to be at least a $2^{\lfloor\frac{(m-1)\sigma}{m}\rfloor+1}$-power residue modulo $p$. The probability that this is true actually equals $2^{-\lfloor\frac{(m-1)\sigma}{m}\rfloor-1}$. Therefore, for large values of $\sigma$ it is quite improbable that our test fails with $b=2$.

Evidently, if $N=H\cdot 2^\sigma+1$ (not being a divisor of $2^H-1$) does not divide a generalized Fermat number of the form $(2^H)^{2^k}+1$ for $1\leq k\leq\sigma-1$, then $N$ is composite. Therefore, under the assumption that $b=2$ is suitable, an algorithm based on Theorem \ref{hauptsatz001K} leads to a primality or compositeness statement for a given $N=H\cdot2^\sigma+1$ with large $\sigma$ after at most $\sigma-1$ squaring and congruence operations and hence runs in $O(\log(N))$.

\medskip

\noindent (4) Perhaps it is useful to consider restrictions of the sequences $\sigma_m$ for $m\geq 3$ in order to get finite subsequences that allow us to use Theorem \ref{hauptsatz001K} for selected exponents $\sigma$ even though $\sigma_m(H)=\infty$.

\begin{thebibliography}{99}

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

\bibitem{berriz}
P. Berrizbeitia, T. G. Berry, and J. Tena-Ayuso, A generalization of Proth's theorem, \textit{Acta Arith.} \textbf{110} (2003), 107--115.

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

\bibitem{caldwell}
C. K. Caldwell and T. Komatsu, Powers of Sierpinski numbers base $B$, \textit{Integers} \textbf{10} (2010), A36, 423--436.

\bibitem{chaumont1}
A. Chaumont and T. M\"uller, All elite primes up to 250 billion, \textit{J. Integer Sequences} \textbf{9} (2006), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL9/Mueller/mueller12.html}{Article 06.3.8}.

\bibitem{chaumont2}
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{cosgrave}
J. B. Cosgrave and K. Dilcher, A role for generalized Fermat numbers, \textit{Math. Comp.}, to appear.

\bibitem{grau}
J. M. Grau, A. M. Oller-Marc\'en, and S. Sadornil, A primality test for $Kp^n+1$ numbers, \textit{Math. Comp.} \textbf{84} (2015), 505--512.

\bibitem{gulliver}
T. A. Gulliver, Self-reciprocal polynomials and generalized Fermat numbers, \textit{IEEE Trans. Inform. Theory} \textbf{38} (1992), 1149--1154.

\bibitem{guthmann}
A. Guthmann, \textit{A generalization of Proth's theorem}. Preprint No.~216,
Universit\"at Kaiserslautern, Fachbereich Mathematik, 1992.

\bibitem{jaroma}
J. H. Jaroma, Equivalence of Pepin's and the Lucas-Lehmer tests, \textit{Eur. J. Pure Appl. Math.} \textbf{2} (2009), 352--360.

\bibitem{kurlberg}
P. Kurlberg and C. Pomerance, On the periods of the linear congruential and power generators, \textit{Acta Arith.} \textbf{119} (2005), 149--169.

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

\bibitem{krizek1}
M. K{\v r}\'{\i}{\v z}ek,
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{krizek2}
M. K{\v r}\'{\i}{\v z}ek,
F. Luca, I. E. Shparlinski, and L. Somer, On the complexity of testing elite primes, \textit{J. Integer Sequences} \textbf{14} (2011), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL14/Krizek/krizek2.html}{Article 11.1.2}.

\bibitem{lucas2}
E. Lucas, Th\'eorie des fonctions num\'eriques simplement p\'eriodiques, \textit{Amer. J. Math.} \textbf{1} (1878), 184--240, 289--321.

\bibitem{muller1}
T. M\"uller, Searching for large elite primes, \textit{Exp. Math.}
\textbf{15} (2005), 183--186.

\bibitem{muller2}
T. M\"uller and A. Reinhart, On generalized elite primes, \textit{J.
Integer Sequences} \textbf{11} (2008), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL11/Mueller/mueller445.html}{Article 08.3.1}.

\bibitem{muller3}
T. M\"uller, A generalization of a theorem by
K{\v r}\'{\i}{\v z}ek,
Luca and Somer on elite
primes, \textit{Analysis (Munich)} \textbf{28} (2008), 375--382.

\bibitem{muller4}
T. M\"uller, On the Fermat periods of natural numbers, \textit{J.
Integer Sequences} \textbf{13} (2010), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL13/Mueller/mueller6.html}{Article 10.9.5}.

\bibitem{pepin}
T. P\'epin, Sur la formule $2^{2^n}+1$, \textit{C. R. Acad. Sci. Paris}
\textbf{85} (1877), 329--331.

\bibitem{proth}
F. Proth, Th\'eor\`emes sur les nombres premiers, \textit{C. R. Acad. Sci. Paris} \textbf{87} (1878), 926.

\bibitem{witno1}
A. Witno, On elite primes of period four, \textit{Int. J. Number Theory} \textbf{6} (2010), 667--671.

\bibitem{witno2}
A. Witno, Primes modulo which almost all Fermat numbers are primitive roots, \textit{Note Mat.} \textbf{30} (2010), 133--140.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11A41; Secondary 11A51, 11B83, 11D61, 11D72, 11Y11.

\noindent \emph{Keywords: } 
exponent, non-trivial divisor, composite number, primality test, prime
number, Diophantine equation, generalized Fermat number, Fermat
period.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000125},
\seqnum{A102742},
\seqnum{A128852},
\seqnum{A272894}, and
\seqnum{A272895}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 12 2016; 
revised version received  December 1 2016.
Published in {\it Journal of Integer Sequences}, December 27 2016.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


.