\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}}} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\ord}{ord} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf On the Fermat Periods of Natural Numbers } \vskip 1cm \large Tom M\"uller\\ Forschungsstelle f\"ur interdisziplin\"are Geisteswissenschaft\\ Institut f\"ur philosophische Bildung\\ Alanus-Hochschule f\"ur Kunst und Gesellschaft\\ Villestr.\ 3\\ 53347 Alfter bei Bonn\\ Germany\\ and \\ Kueser Akademie f\"ur europ\"aische Geistesgeschichte\\ Gestade 18\\ 54470 Bernkastel-Kues\\ Germany \\ \href{mailto:tom.mueller@alanus.edu}{\tt tom.mueller@alanus.edu} \\ \end{center} \vskip .2 in \begin{abstract} Let $b>1$ be a natural number and $n\in\mathbb{N}_0$. Then the numbers $F_{b,n}:=b^{2^n}+1$ form the sequence of generalized Fermat numbers in base $b$. It is well-known that for any natural number $N$, the congruential sequence ($F_{b,n}$ (mod $N$)) is ultimately periodic. We give criteria to determine the length of this Fermat period and show that for any natural number $L$ and any $b>1$ the number of primes having a period length $L$ to base $b$ is infinite. From this we derive an approach to find large non-Proth elite and anti-elite primes, as well as a theorem linking the shape of the prime factors of a given composite number to the length of the latter number's Fermat period. \end{abstract} \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} \section{Introduction} Let $N$ and $b>1$ be natural numbers. For $n\in\mathbb{N}_0$ denote by $F_{b,n}:=b^{2^n}+1$ the terms of the sequence of generalized Fermat numbers in base $b$. The numbers $F_{b,n}$ obviously fulfill the recurrence relation \begin{eqnarray}\label{recu} F_{b,n+1}=\left(F_{b,n}-1\right)^2+1. \end{eqnarray} This immediately implies that the sequence $0\leq f_n< N$ defined by $f_n\equiv F_{b,n}$ (mod $N$) is ultimately periodic. So, there exist two minimal natural numbers $s$ and $L$ such that $f_{s}=f_{s+kL}$ for all $k\in\mathbb{N}$. Then we call the terms $f_s, f_{s+1}, \ldots, f_{s+L-1}$ the $b$-\textit{Fermat remainders} of $N$. Moreover, we say that the natural number $N$ has a $b$-\textit{Fermat period} of length $L$ beginning with the Fermat number $F_{b,s}$. We shall denote the length of the $b$-Fermat period of the natural number $N$ by $L_b(N)$ throughout this paper. Notice that, from another point of view, the Fermat remainders may be considered to be a special case of power generators. The statistical properties of the period lengths appearing in this standard method to generate pseudorandom numbers have been studied by several authors in the past years, e.g., by Kurlberg and Pomerance~\cite{kurlberg}, who give new results together with a review of the present knowledge of this matter. In his 1986 paper, Aigner~\cite{aigner} gave a complete characterization of $s$ and $L$ for prime numbers $N$ in the case $b=2$. That result was generalized for all bases $b>1$ by the author and Reinhart~\cite{muller4}. The purpose of the present paper is to give a complete characterization of $L_b(N)$ for all bases $b>1$ and all natural numbers $N$. To that respect, we show some multiplicative laws allowing us to compute $L_b(N)$ for composite $N$ using the respective period lengths of its prime factors. This demands for a closer look to $L_b(p)$ for prime numbers $p$ and selected bases $b$. Moreover, we prove that for every $b>1$ and every natural number $l$ the set $\mathcal{F}_b(l)$ is infinite. Here, $\mathcal{F}_b(l):=\{p\in\mathbb{P}:L_b(p)=l\}$ denotes the set of all prime numbers with a $b$-Fermat period of length $l$. Finally, we present two possible applications of these theoretical approaches. First, the numbers considered in the infinity proof can be used to provide prime numbers with given period lengths. We examine several of these numbers in order to find large non-Proth elite and anti-elite prime numbers. Secondly, the multiplicative laws for $L_b(N)$ show that every composite number preserves a part of information on the periodical behavior of its prime factors. This could be -- as we illustrate in one single example -- used to develop or support methods of factorization. \section{The Fermat period of natural numbers} The theorem of Aigner can be generalized for every natural number $N$ that is relatively prime to the given base $b>1$. \newtheorem{theo1}{Theorem}[section] \begin{theo1}\label{aigner} Let $N$ and $b>1$ be natural numbers with $\gcd(N,b)=1$. Write the multiplicative order of $b$ modulo $N$ as $\ord_N(b)=2^s\cdot t$ with $s \in \mathbb{N}_0$ and $t$ an odd number. Then the $b$-Fermat period of $N$ begins with the Fermat number $F_{b,s}$. The length $L_b(N)$ of the $b$-Fermat period equals the multiplicative order of $2$ modulo $t$. \end{theo1} The proof of Theorem \ref{aigner} works in total analogy to that of Theorem 2.6 in the paper of M\"uller and Reinhart~\cite{muller4}. \begin{remark} If $N$ is a prime number of the form $2^r\cdot h+1$ with $r\in\mathbb{N}$ and $h$ odd, it is obvious that the parameters of the multiplicative order of $b$ modulo $N$, i.e., $2^s\cdot t$, fulfill $0\leq s\leq r$ and $t|h$. \end{remark} The question of the period length $L_b(N)$ remains open for the case $\gcd(N,b)>1$ yet. It is resolved by the following results. \theoremstyle{theorem} \newtheorem{theo1a}[theo1]{Lemma} \begin{theo1a}\label{2potenz} Let $b>1$ and $n$ be natural numbers. Then $L_b(2^n)=1$. \end{theo1a} \begin{proof} If $b$ is even we immediately get $b^{2^m}+1\equiv 1$ (mod $2^n$) for all $m$ with $2^m>n$. It follows $L_b(2^n)=1$.\\ For odd $b$ we have $\gcd(b,2^n)=1$ such that the theorem of Euler guarantees \begin{eqnarray} b^{2^{n-1}}+1\equiv b^{\phi(2^n)}+1\equiv 2 \quad (\bmod \, 2^n), \end{eqnarray} and hence by recurrence relation (\ref{recu}) we have $F_{b,m}\equiv 2$ (mod $2^n$) for all $m\geq n-1$. This again leads to $L_b(2^n)=1$. \end{proof} \newtheorem{theo1b}[theo1]{Lemma} \begin{theo1b}\label{ppotenz} Let $p$ be an odd prime number. Let $a$ and $n$ be natural numbers. Then $L_{ap}(p^n)=1$. \end{theo1b} \begin{proof} We have $(ap)^{2^m}+1\equiv 1$ (mod $p^n$) for all $m$ with $2^m\geq n$. From this follows the claim. \end{proof} \newtheorem{theo1c}[theo1]{Lemma} \begin{theo1c}\label{wegdamit} Let $b>1$ and $n$ be natural numbers. Write $n=am$ such that for every prime factor $p$ of $a$ we have $p|b$ and $\gcd(b,m)=1$. Then $L_b(n)=L_b(m)$. \end{theo1c} \begin{proof} The conditions of the lemma lead to the congruential system \begin{eqnarray*} \begin{cases} F_{b,k} \equiv 1 \, (\bmod\, a)\\ F_{b,k} \equiv \lambda_k \, (\bmod\, m) \end{cases} \end{eqnarray*} for all indices $k$ large enough. The Chinese remainder theorem states that then there exists an unique solution to this system of the form $F_{b,k}\equiv \Lambda_k$ (mod $n$). Because of the periodicity we have $F_{b,k+L_b(m)}\equiv F_{b,k}\equiv \lambda_k$ (mod $m$) and hence $F_{b,k+L_b(m)}\equiv \Lambda_K\equiv F_{b,k}$ (mod $n$). This implies $L_b(m)\geq L_b(n)$. Moreover, we get $F_{b,k+L_b(n)}\equiv F_{b,k}$ (mod $n$). Since $m|n$ we obtain from this latter congruence $F_{b,k+L_b(n)}\equiv F_{b,k}$ (mod $m$), i.e., $L_b(m)\leq L_b(n)$. This proves the claim. \end{proof} \newtheorem{theo2}[theo1]{Lemma} \begin{theo2}\label{lemmageschier} Let $b>1$ be a natural number. Let $n$ and $m$ be coprime natural numbers. Then $L_b(nm)=\lcm(L_b(n),L_b(m))$. \end{theo2} \begin{proof} First we study the case $\gcd(n,b)=\gcd(m,b)=1$. Write $2^{s_n}t_n$ the multiplicative order of $b$ modulo $n$ and $2^{s_m}t_m$ the multiplicative order of $b$ modulo $m$. Then by Theorem \ref{aigner} we know that $L_b(n)=\ord_{t_n}(2)$ and $L_b(m)=\ord_{t_m}(2)$. Using a well-known result from elementary number theory, we get \begin{eqnarray*} \ord_{nm}(b) & = & \lcm(\ord_n(b),\ord_m(b))\\ & = & \lcm(2^{s_n}t_n,2^{s_m}t_m)\\ & = & 2^s \lcm(t_n,t_m), \end{eqnarray*} where $s:=\max\{s_n,s_m\}$. Moreover, it is well-known that $\ord_{\lcm(t_n,t_m)}(2)=\lcm(\ord_{t_n}(2),\ord_{t_m}(2))$. Again with Theorem \ref{aigner} we then obtain \begin{eqnarray*} L_b(nm) & = & \ord_{\lcm(t_n,t_m)}(2)\\ & = &\lcm(\ord_{t_n}(2),\ord_{t_m}(2))=\lcm(L_b(n),L_b(m)). \end{eqnarray*} Secondly we examine the case $\gcd(n,b),\gcd(m,b)\geq 1$. Write $n=a_n\nu$ and $m=a_m\mu$ such that for every prime factor $p$ of $a_n$ we have $p|b$ and $\gcd(b,\nu)=1$ and such that for every prime factor $q$ of $a_m$ we have $q|b$ and $\gcd(b,\mu)=1$. By Lemma \ref{wegdamit} we know that $L_b(nm)=L_b(\nu\mu)$. Notice that $\gcd(\nu,\mu)=1$. So, the first part of the present proof guarantees that $L_b(\nu\mu)=\lcm(L_b(\nu),L_b(\mu))$. Again with Lemma \ref{wegdamit} this finally gives $L_b(nm)=\lcm(L_b(n),L_b(m))$. \end{proof} Using induction over the number of different prime factors of $N$, this latter result can be easily generalized. \newtheorem{conss1}[theo1]{Consequence} \begin{conss1}\label{lrechnung} Let $b>1$ be a natural number. Let $N=\prod_{\nu=1}^r p_\nu^{\alpha_\nu}$ be the canonical prime factorization of the natural number $N>1$. Then $$L_b(N)=\lcm(L_b(p_1^{\alpha_1}),L_b(p_2^{\alpha_2}),\ldots,L_b(p_r^{\alpha_r})).$$ \end{conss1} Furthermore, if we define $L_b(1):=1$, we obtain a complete characterization of $L_b(N)$ for every base $b>1$ and every natural number $N$. \theoremstyle{remark} \newtheorem{rem2}[theo1]{Remark} \begin{rem2} Let $n,m,b>1$ be natural numbers with $\gcd(nm,b)=1$. If the $b$-Fermat period of $n$, (resp., $m$) begins with the term $F_{b,s_n}$ (resp., $F_{b,s_m}$) then the $b$-Fermat period of the number $nm$ begins with the term $F_{b,\max\{s_n,s_m\}}$. \end{rem2} \theoremstyle{theorem} \section{The infinity of the sets $\mathcal{F}_b(L)$} The following necessary condition for a prime number $p$ to have a $b$-Fermat period of length $L$ is known~\cite{muller4}. \newtheorem{theo20}{Theorem}[section] \begin{theo20}\label{theo2a} Let $p=2^r\cdot h+1$ be a prime number with a natural number $r\geq 1$ and $h$ odd. Let $b>1$ be a natural number. If $p$ has a $b$-Fermat period of length $L>1$ then $p$ is a divisor of the number \begin{eqnarray} N_{b,r}^{(L)}:=\sum_{n=0}^{2^L-2} (F_{b,r}-1)^n. \end{eqnarray} \end{theo20} We will use Theorem \ref{aigner} and the latter result to show that for all natural numbers $L$ and for every base $b>1$ there are infinitely many prime numbers $q$ having a $b$-Fermat period of length $L$. For $L=1$ this claim is trivial since it is well-known that the odd parts of the Fermat numbers $F_{b,n}$ are pairwise coprime and for every odd prime divisor $p$ of a given $F_{b,m}$ equation (\ref{recu}) implies $F_{b,n}\equiv 2$ (mod $p$) for all $n>m$, i.e., we get $L=1$ for infinitely many primes.\\ \subsection{Factors of the numbers $N_{b,r}^{(L)}$} Notice that the condition in Theorem \ref{theo2a} is not sufficient for $p$ to have a $b$-Fermat period of length $L>1$. In fact, if $p=2^rh+1$ is a factor of $N_{b,r}^{(L)}$ then every positive divisor of $L$ could be the length of the $b$-Fermat period of $p$ too. In the proof of Theorem \ref{theo2a} one makes use of the fact that if $L$ is the length of the period then $F_{b,r+L}\equiv F_{b,r}$ (mod $p$), i.e., there exists a natural number $c$ with $c+1\equiv F_{b,r}$ (mod $p$) and $c^{2^L}\equiv c$ (mod $p$). From this follows (by excluding the cases $c\equiv 0$ and $c\equiv 1$ (mod $p$) leading to period length 1) that $p$ divides $N_{b,r}^{(L)}$. But for every natural number $k$ we obtain, because of the definition of $L$, that $c^{2^{Lk}}\equiv c$ (mod $p$) and hence in total analogy to the previous argument that $p$ is a divisor of $N_{b,r}^{(Lk)}$ as well. The other way around, if $L>1$ is the length of the $b$-Fermat period of $p=2^rh+1$ we have $p\,|\,N_{b,r}^{(L)}$, i.e., $c^{2^L}\equiv c$ (mod $p$). Like in Theorem \ref{aigner} we write $2^st$ the multiplicative order of $b$ modulo $p$. This implies that there cannot be a natural number $m L$. Then we get the congruence $c^{2^{L(L_1-L)}-1}\equiv 1$ (mod $p$). This is equivalent to the fact that the multiplicative order of $c$ modulo $p$ divides the difference of the exponents, i.e., the number $2^L(2^{L_1-L}-1)$. As we have $c\equiv b^{2^r}$ (mod $p$), the multiplicative order of $c$ modulo $p$ equals $t$. Hence $2^{L_1-L}\equiv 1$ (mod $t$), which implies that the multiplicative order of $2$ modulo $t$, i.e., $L$, is a divisor of the exponent $L_1-L$. So, we finally have $L_1\equiv 0$ (mod $L$). All this shows that the following theorem holds. \newtheorem{theo3}[theo20]{Theorem} \begin{theo3}\label{theo3a} Let $b>1$ be a natural number. Let $p=2^rh+1$ be a prime number dividing $N_{b,r}^{(K)}$ for a natural number $K$. Then the length $L$ of the $b$-Fermat period of $p$ is a divisor of $K$. \end{theo3} In order to prove our main result we need the following factorization formula \begin{eqnarray}\label{12345} N_{b,r+1}^{(L)}= N_{b,r}^{(L)}\left(N_{b,r}^{(L)}- 2 \sum_{n=0}^{2^{L-1}-2}(F_{b,r}-1)^{2n+1}\right). \end{eqnarray} The truth of this can be seen as follows. Let $R\geq 0$ be an even number and let $x$ be a natural number. Using the properties of geometric sums we get \begin{eqnarray}\label{eq3} \sum_{n=0}^R x^n \cdot \sum_{n=0}^R (-x)^n = \sum_{n=0}^R x^{2n}. \end{eqnarray} Notice that all three sums of this latter equation actually are odd numbers. Moreover, we see that \begin{eqnarray} \sum_{n=0}^R x^n & = & 1 + (x+1)\sum_{n=0}^{\frac{R}{2}-1}x^{2n+1}\label{here5} \end{eqnarray} and \begin{eqnarray}\label{happy} \sum_{n=0}^R (-x)^n = \sum_{n=0}^R x^n - 2 \sum_{n=0}^{\frac{R}{2}-1}x^{2n+1}. \end{eqnarray} If we now define $x:=b^{2^r}=(F_{b,r}-1)$ and $R:=2^L-2$ this leads to formula (\ref{12345}). Denote by $d$ the greatest common divisor of the numbers $\sum_{n=0}^R x^n$ and $\sum_{n=0}^R (-x)^n$. Then $d$ must be odd and we obtain by (\ref{happy}) that $d$ is a divisor of $\sum_{n=0}^{\frac{R}{2}-1}x^{2n+1}$ as well. With (\ref{here5}) this leads to \begin{eqnarray} 0\equiv \sum_{n=0}^R x^n \equiv 1 \quad (\bmod\, d), \end{eqnarray} which is possible if and only if $d=1$. Hence the numbers $N_{b,r}^{(L)}$ and $Q_{b,r}^{(L)}:=N_{b,r+1}^{(L)}/N_{b,r}^{(L)}$ are coprime for all $r$. Moreover, the sequence $Q_{b,n}^{(L)}$ ($n\in\mathbb{N}_0$) consists of pairwisely coprime terms. \subsection{The main result} \newtheorem{theo21}[theo20]{Lemma} \begin{theo21}\label{theo21a} Let $b>1$ be a natural number. Let $L$ be a prime number. Then there are infinitely many prime numbers with a $b$-Fermat period of length $L$. \end{theo21} \begin{proof} Let $L$ be a prime number. We already know that the terms of the sequence $Q_{b,r}^{(L)}$ are pairwisely coprime. This means that there are infinitely many prime numbers being factors of the numbers $N_{b,r}^{(L)}$ $(r\in\mathbb{N})$. Let $p$ be such a prime number. By Theorem \ref{theo3a} we know that the length of the $b$-Fermat period of $p$ is a divisor of $L$, i.e., $1$ or $L$. The first case implies $x^2\equiv x$ (mod $p$) for $x\equiv b^{2^r}$ (mod $p$). From this follows $x(x-1)\equiv 0$ (mod $p$), i.e., either $x\equiv 0$ (mod $p$) or $x\equiv 1$ (mod $p$). Now, $x\equiv b^{2^r}\equiv 0$ (mod $p$) implies $b\equiv 0$ (mod $p$), which is only possible for the finite number of prime factors of $b$. From $x\equiv 1$ (mod $p$) follows that $N_{b,r}^{(L)}\equiv 2^L-1\equiv 0$ (mod $p$), i.e., $p$ is an element of the finite set of all prime factors of the number $2^L-1$. All in all, only a finite number of primes dividing one of the numbers $N_{b,r}^{(L)}$ have a $b$-Fermat period of length 1. Hence, all the remaining primes dividing the terms $N_{b,r}^{(L)}$ ($r\in\mathbb{N}$) must have a Fermat period of length $L$. \end{proof} \newtheorem{theo07}[theo20]{Theorem} \begin{theo07}\label{theo22a} Let $b>1$ and $L$ be natural numbers. Then the set $\mathcal{F}_b(L)$ is infinite. \end{theo07} \begin{proof} For $L=1$ we have $\mathcal{F}_b(1)=\{p\in\mathbb{P}: p|F_{b,r} \text{ for } r\in\mathbb{N}\}$. It is well-known that this latter set is infinite.\\ If $L$ is a prime number this is the claim of Lemma \ref{theo21a}. So let $L>1$ be a composite number in the following. We again consider the numbers \begin{eqnarray*} N_{b,r}^{(L)}=\sum_{\nu=0}^{2^L-2}\left(b^{2^r}\right)^\nu \text{ and } Q_{b,r}^{(L)}=\sum_{\nu=0}^{2^L-2}\left(-b^{2^r}\right)^\nu \end{eqnarray*} for $r\in\mathbb{N}$. In order to prove the claim of the theorem, we have to show that for all $r$ large enough the numbers $Q_{b,r}^{(L)}$ have a prime divisor $p$ not dividing any number $Q_{b,s}^{(d)}\not=Q_{b,r}^{(L)}$ with $s\leq r$ and $d|L$.\\ First, we consider the case $s 1$ and $h$ odd. Then $p$ has a $2$-Fermat period of length $L=4$ if and only if $p$ is a divisor of the number \begin{eqnarray} W_r:=\frac{1}{5}\cdot \sum_{\nu=0}^4 \left(2^{2^r\cdot 3}\right)^\nu. \end{eqnarray} If $r=1$ the only prime numbers with a $2$-Fermat period of length $L=4$ are $11$, $31$, $151$ and $331$. \end{coro32} \begin{proof} The case $r=1$ is trivial. Consider now $r\geq 2$. We know that all the primes of the form $p=2^r\cdot h+1$ with a period length $L=4$ divide the term \begin{eqnarray*} N_{2,r}^{(4)}=N_{2,r}^{(2)}\cdot \sum_{\nu=0}^4 \left(2^{2^r\cdot 3}\right)^\nu. \end{eqnarray*} All primes dividing $N_{2,r}^{(4)}$ and having a Fermat period of length $2$ must also divide $N_{2,r}^{(2)}$. So the numbers we are looking for are all the prime divisors of the term $$V_r:=\sum_{\nu=0}^4 \left(2^{2^r\cdot 3}\right)^\nu$$ not having a Fermat period of length 1 or 2. The first kind of primes again must be divisors of the numbers $b=2$ or $2^L-1=15$, i.e., 2, 3 or 5. The second kind of primes consists of common prime divisors of the numbers $N_{2,r}^{(2)}$ and $V_r$. Suppose $p$ to be such a prime number. Then \begin{eqnarray*} 2^{2^r\cdot3} & = & 2^{2^r\cdot3} + N_{2,r}^{(2)} - N_{2,r}^{(2)}\\ & = & 2^{2^r}N_{2,r}^{(2)}-N_{2,r}^{(2)}+1 \equiv 1 \quad (\bmod\, p). \end{eqnarray*} This leads to $0\equiv V_r\equiv 5$ (mod $p$) for all common prime divisors of $N_{2,r}^{(2)}$ and $V_r$. Therefore, only the primes $2$, $3$ and $5$ have to be considered here. All three have a $2$-Fermat period of length 1. As $V_r$ is odd the first candidate is not a divisor, as well as $3$ since $V_r\equiv 2$ (mod $3$) for all natural numbers $r\geq 1$. An easy computation shows that $V_r\equiv 0$ (mod $5$) and $V_r\equiv 5$ (mod $25$) for all $r\geq 2$. Hence, the number $\frac{V_r}{5}$ is divided only by numbers having a period length $L=4$. This proves the corollary. \end{proof} These two corollaries can be used to find prime numbers with $2$-Fermat periods of the lengths 3 or 4, and furthermore to find elite or anti-elite primes. A $b$-\textit{elite} prime number $p$ is a prime number none of whose $b$-Fermat remainders is a quadratic residue modulo $p$. If all the $b$-Fermat remainders are quadratic residues modulo a prime number $p$ then $p$ is called a $b$-\textit{anti-elite} prime~\cite{generali}. If $b=2$, we simply speak of elite or anti-elite primes. In the past years a number of papers on these two families of prime numbers have been published~\cite{aigner,chaumont,chaumont1,kri,muller,muller2,witno}. There have been two approaches to compute elites, resp., anti-elites. A first way consisted in checking all prime numbers of a given interval for eliteness, resp., anti-eliteness. As a result of such researches all 27 elite primes up to $2.5\cdot10^{12}$ are known~\cite{chaumont1}, as well as all 84 anti-elite primes up to $10^{11}$~\cite{muller2}. These prime numbers are summarized in sequence \seqnum{A102742}, resp., sequence \seqnum{A128852} of Sloane's \textit{On-Line Encyclopedia of Integer Sequences}~\cite{sloane}. Recently, Dennis R. Martin completed the search for elite and anti-elite primes up to $10^{14}$. He found two new elite primes and 29 new anti-elite primes~\cite{martin1}. In a second approach only large primes of the easy-to-check Proth type $2^r\cdot h+1$ with rather small $h<2^r$ were examined in order to find large primes having relatively small Fermat periods, which then were checked for eliteness. That way, some 60 elite primes larger than $2.5\cdot 10^{12}$ could be found, the largest of which have more than $300000$ decimal digits~\cite{chaumont1}. No elite prime larger than $10^{12}$ and not being a Proth number was known until the year 2008. Using the Corollary \ref{coro32a} we can find one such prime with 35 decimal digits. Furthermore, a non-Proth anti-elite prime with 14 decimal digits can be found. For this we consider the prime factorization of the number $W_5$ which is given by \begin{eqnarray*} W_5 & = & 11\cdot31\cdot41\cdot61\cdot151\cdot331\cdot1321\cdot23041\cdot61681\cdot414721\cdot\\ && 394783681\cdot4278255361\cdot4562284561\cdot46908728641\\ && \cdot44479210368001\cdot14768784307009061644318236958041601. \end{eqnarray*} Let us have a look at the factors $p:=14768784307009061644318236958041601$ and $q:=44479210368001$. Notice that their primality can be established, e.g., by the well-known method of Brillhart, Lehmer and Selfridge~\cite{brillart}. We obtain $$p=2^9\cdot28845281849627073524059056558675+1$$ and $$q=2^{10}\cdot 43436728875+1.$$ A simple computation shows that $p$ provides four Fermat remainders each being a quadratic non-residue modulo $p$, while all four Fermat remainders of $q$ are quadratic residues modulo $q$, i.e., $p$ is an elite and $q$ an anti-elite prime number. Investing more computational effort into the rather time-consuming factorization of the numbers $W_r$ could probably lead to the discovery of even larger non-Proth elite or anti-elite primes. Moreover, we find the non-Proth elite prime $$p=1475204679190128571777=2^7\cdot 11525036556172879467+1$$ with period length $L=6$ considering the prime factors of the integer number $\frac{N_{2,3}^{(6)}}{\text{lcm}(N_{2,3}^{(2)},N_{2,3}^{(3)})}$. \theoremstyle{remark} \newtheorem{rem4}[coro31]{Remark} \begin{rem4} A fourth way of computing elite primes was recently proposed by ``Eigenray'' in a forum on the pages of UC Berkeley (compare the URL~\cite{eigenray}; valid as of July 8, 2008). It is considered to search for elite primes among the factors of the values of the $5\cdot 2^s$-th cyclotomic polynomial evaluated at 2. The following elite primes were found that way by the author of the forum entry: \begin{eqnarray} s=7 & : & p_1 = 3442404051886487041\\ s=8 & : & p_2 = 7771646317471635593256655841281,\\ && p_3 = 2^{10}\cdot C99 + 1 \label{asdf}\\ s=9 & : & p_4 = 46454107161999112389551048616961\\ s=10 & : & p_5 = 3587745015951361 \end{eqnarray} In line (\ref{asdf}), the number \begin{eqnarray*} C99 & = & 51233969525206267191459826792872621224191144511286\text{-}\\ & & 8396608612454598970667762655058642306684254536535 \end{eqnarray*} is an odd composite number with 99 decimal digits; $p_3$ is a prime with 102 decimal digits. The similar approach has lately also been discussed by Witno~\cite{witno}. Notice that all the primes presented here are non-Proth elite primes with $L=4$. This supports a conjecture about non-Proth elite primes proposed by Chaumont et al.~\cite{chaumont1}. \end{rem4} \theoremstyle{theorem} \subsection{Factors of composite numbers} A second application could lie in the field of factoring natural numbers. The following theorem connects the shape of a prime number $p$ with the information on $b$-Fermat period lengths preserved in every composite number being a multiple of $p$. \newtheorem{theo100}[coro31]{Theorem} \begin{theo100}\label{mersennefact} Let $N$ be an odd composite number. Then every prime factor $p$ of $N$ is of the form $p=2^r\cdot k\cdot \delta+1$ with $r\in\mathbb{N}$, $k$ odd and $\delta$ a divisor of $2^{L_b(N)}-1$ for any given natural number $b>1$, i.e., $\delta$ is a divisor of the $L_b(N)$-th Mersenne number. \end{theo100} \begin{proof} If $p$ is a divisor of $N$ then $L_b(p)$ is a divisor of $L_b(N)$ as well. This can be seen by combining the above-mentioned Consequence \ref{lrechnung} and Theorem \ref{theo3a}. Now write $p=2^r\cdot h+1$ where $r$ is a natural number and $h$ is odd. Then we know by Aigner's theorem that there exists a divisor $\delta$ of $h$, i.e., $h=k\cdot \delta$ for some appropriate $k$, with $L_b(p)=\ord_{\delta}(2)$. Therefore, we get $p=2^rk\delta+1$ with $2^{L_b(p)}\equiv 1$ (mod $\delta$). This completes the proof. \end{proof} \theoremstyle{remark} \newtheorem{ex}[coro31]{Example} \begin{ex} Consider the 74-decimal-digit natural number \begin{eqnarray*} N & := & 96493407697763496186309154173906589877\text{-}\\ & & 72498722136713669954798667326094136661. \end{eqnarray*} If one finds out that this number equals $N_{2,1}^{(7)}$ it is trivial to give the factorization $N=N_{2,0}^{(7)}\cdot Q_{2,0}^{(7)}$. If one is lacking this piece of information, the task of factoring the number $N$ is not at all that easy. As a reference, we use the standard integer factorization routine (\texttt{ifactor}) given in MAPLE 11. Optionally, this command can be used with an additional parameter allowing to run factorization algorithms based on D. Shanks' undocumented square-free factorization, Lenstra's elliptic curve method or on Pollard's Rho method. All these methods are not able to factorize $N$ within 120 seconds on a PC powered by an AMD Sempron 2600 XP+ processor. Now, the MAPLE-implementation of Pollard's Rho method allows to add another parameter. If we know that one of the searched prime factors $p$ is of the form $p\equiv 1$ (mod $\delta$) we can run the command \texttt{ifactor(N,pollard,$\delta$)} in order to increase the efficiency of the method. A simple computation checking the congruences $F_{2,n}$ (mod $N$) for the indices $n\in\{1,2,\ldots,8\}$ shows that $L_2(N)=7$. So, by Theorem \ref{mersennefact} every prime factor $p$ of $N$ has to fulfill $p\equiv 1$ (mod $\delta$) for some $\delta$ dividing $2^7-1=127$. As 127 is a prime and $\delta=1$ only leads to a period length of $1$, we obtain $\delta=127$ here. Running the command \texttt{ifactor(N,pollard,127)} gives the prime factorization $N=N_{2,0}^{(7)}\cdot Q_{2,0}^{(7)}$ in less than one hundredth of a second. \end{ex} This one example may suffice here. Deeper insights in whether this approach might be worth of further considerations have to be brought to light by forthcoming studies. Maybe this is a first small step towards a ``statistical" factorization approach. \section{Acknowledgements} The author wants to thank Dr. Markus Nie\ss\, from the Catholic University of Eichst\"att-Ingolstadt for his help with the MAPLE-computations. Moreover, the author is grateful to the friendly referee who made very valuable suggestions to improve this 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{brillart} J. Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^m\pm 1$, \textit{Math. Comp.} \textbf{29} (1975), 620--647. \bibitem{carmichael} R. D. Carmichael, On the numerical factors of the arithmetic forms $\alpha^n\pm\beta^n$, \textit{Ann. of Math.} \textbf{15} (1913), 30--70. \bibitem{chaumont} A. Chaumont and T. M\"uller, All elite primes up to 250 billion, \textit{J. Integer Seq.} \textbf{9} (2006), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Mueller/mueller12.html}{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{eigenray} ``Eigenray'', Forum entry, available online at\\ \texttt{http://www.ocf.berkeley.edu/\symbol{126}wwu/cgi-bin/yabb} \\ {\tt /YaBB.cgi?board=riddles}\verb|_|\texttt{putnam;action=display;num=1204796915} (valid as of July 8, 2008). \normalsize \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{kurlberg} P. Kurlberg and C. Pomerance, On the periods of linear congruential and power generators. \textit{Acta Arith.} \textbf{119} (2005), 149--169. \bibitem{martin1} D. R. Martin, Elite prime search and anti-elite prime search, published online: \href{http://www.primenace.com/papers/math/ElitePrimes.htm}{\tt http://www.primenace.com/papers/math/ElitePrimes.htm} and \href{http://www.primenace.com/papers/math/Anti-ElitePrimes.htm}{\tt http://www.primenace.com/papers/math/Anti-ElitePrimes.htm} (valid as of July 28, 2010). \bibitem{muller} T. M\"uller, Searching for large elite primes, \textit{Experiment. Math.} \textbf{15} (2006), 183--186. \bibitem{muller2} T. M\"uller, On anti-elite prime numbers, \textit{J. Integer Seq.} \textbf{10} (2007), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Mueller/mueller56.html}{Article 07.9.4}. \bibitem{muller4} T. M\"uller and A. Reinhart, On generalized elite primes. \textit{J. Integer Seq.} \textbf{11} (2008), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Mueller/mueller445.html}{Article 08.3.1}. \bibitem{generali} T. M\"uller, A generalization of a theorem by K\v r\' i\v zek, Luca and Somer on elite primes. \textit{Analysis (Munich)} \textbf{28} (2008), 375--382. \bibitem{sloane} N. J. A. Sloane, Online Encyclopedia of Integer Sequences (OEIS), available at \href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/\symbol{126}njas/sequences/}. \bibitem{witno} A. Witno, On elite primes of period four, \textit{Int. J. Number Theory} \textbf{6} (2010), 667--671. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11A41; Secondary 11A51, 11N69, 11Y05. \noindent \emph{Keywords: } Generalized Fermat number; elite prime number; anti-elite prime number; Fermat period. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A102742} and \seqnum{A128852}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received August 7 2010; revised version received October 11 2010; November 6 2010. Published in {\it Journal of Integer Sequences}, December 7 2010. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}