\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 Primes in Classes of the \\ \vskip .2in Iterated Totient Function } \vskip 1cm \large Tony~D.~Noe\\ 14025~NW~Harvest~Lane\\ Portland,~OR~~97229\\ USA\\ \href {mailto:noe@sspectra.com} {\tt noe@sspectra.com} \end {center} \vskip .2in \begin {abstract} As shown by Shapiro, the iterated totient function separates integers into classes having three sections. After summarizing some previous results about the iterated totient function, we prove five theorems about primes $p$ in a class and the factorization of~$p-1$. An application of one theorem is the calculation of the smallest number in classes up to~1000. \end {abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \section {Introduction} Let $\phi(x)$ denote Euler's totient function. Defining $\phi^0(x)=x$, the iterated totient function is defined recursively for $n>0$ by $\phi^n(x) = \phi( \phi^{n-1}(x))$. For $x>1$, $\phi(x)2^{C(x)}$. \item For any integer $x$, $2^{C(x)} < x \le 2 \cdot 3^{C(x)}$. \end {enumerate} Thus, Shapiro proves that numbers $x$ in class $n>1$ fall into three sections: $$2^n < x < 2^{n+1}, \quad \quad 2^{n+1} \le x \le 3^n, \quad \quad 3^n < x \le 2 \cdot 3^n.$$ Table~\ref {Ta2} shows numbers separated into the three sections. Shapiro establishes the following properties of these classes: \begin {table} \begin {center} {\footnotesize \begin {tabular} [b] {|c|l|l|l|} \hline & & & \\[-6pt] Class & \qquad \quad Section I & \qquad \qquad \qquad \quad Section II & \quad ~Section III \\ & & & \\[-6pt] \hline 0 & 1, & 2, & \\ 1 & 3, & 4, & 6, \\ 2 & 5, 7, & 8, 9, & 10, 12, 14, 18, \\ 3 & 11, 13, 15, & 16, 19, 20, 21, 22, 24, 26, 27, & 28, 30, 36, 38, 42, \\ & & & 54, \\ 4 & 17, 23, 25, 29, 31, & 32, 33, 34, 35, 37, 39, 40, 43, 44, 45, 46, 48, & 84, 86, 90, 98, 108, \\ & & 49, 50, 52, 56, 57, 58, 60, 62, 63, 66, 70, 72, & 114, 126, 162, \\ & & 74, 76, 78, 81, & \\ 5 & 41, 47, 51, 53, 55, 59, 61, & 64, 65, 67, 68, 69, 71, 73, 75, 77, 79, 80, 82, & 252, 254, 258, 266, \\ & & 87, 88, 91, 92, 93, 94, 95, 96, 99, 100, 102, & 270, 294, 324, 326, \\ & & 104, 105, 106, 109, 110, 111, 112, 116, 117, & 342, 378, 486,\\ & & 118, 120, 122, 124, 127, 129, 130, 132, 133, & \\ & & 134, 135, 138, 140, 142, 144, 146, 147, 148, & \\ & & 150, 152, 154, 156, 158, 163, 168, 171, 172, & \\ & & 174, 180, 182, 186, 189, 190, 196, 198, 210, & \\ & & 216, 218, 222, 228, 234, 243, & \\ \hline \end {tabular}} \caption {Numbers in Classes 0 to 5 Organized by Section} \label {Ta2} \end {center} \end {table} \begin {enumerate} \item [8.] Numbers in section I are odd. \item [9.] Numbers in section II are even or odd. \item [10.] Numbers in section III are even. \item [11.] If integer $x$ is in section I, then every divisor of $x$ is in section~I of its class. \end {enumerate} This last property~\cite [Theorem 15] {Shapiro} is most interesting. For example, it tells us that the factors~5 and~11 of~55 must both be in section~I because~55 is in section~I. Table~\ref {Ta3} shows Section~I numbers (sequence \seqnum{A005239}); each composite number, shown in bold, has all its factors in section~I. \begin {table} [H] \begin {center} {\footnotesize \begin {tabular} [b] {|c|l|} \hline & \\[-6pt] Class & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad Numbers in Section I \\ & \\[-6pt] \hline 0 & 1, \\ 1 & 3, \\ 2 & 5, 7, \\ 3 & 11, 13, \textbf{15}, \\ 4 & 17, 23, \textbf{25}, 29, 31, \\ 5 & 41, 47, \textbf{51}, 53, \textbf{55}, 59, 61, \\ 6 & 83, \textbf{85}, 89, 97, 101, 103, 107, 113, \textbf{115}, \textbf{119}, \textbf{121}, \textbf{123}, \textbf{125}, \\ 7 & 137, 167, 179, \textbf{187}, 193, \textbf{205}, \textbf{221}, 227, 233, \textbf{235}, 239, 241, \textbf{249}, 251, \textbf{253}, \textbf{255}, \\ 8 & 257, \textbf{289}, 353, 359, 389, \textbf{391}, 401, 409, \textbf{411}, \textbf{415}, \textbf{425}, 443, \textbf{445}, 449, \textbf{451}, 461, 467, 479,... \\ 9 & 641, \textbf{685}, \textbf{697}, 719, 769, \textbf{771}, 773, \textbf{799}, 809, 821, 823, \textbf{835}, 857, \textbf{867}, 881, 887, \textbf{895}, \textbf{901},... \\ 10 & 1097, 1283, \textbf{1285}, 1361, 1409, \textbf{1411}, 1433, 1439, \textbf{1445}, \textbf{1507}, \textbf{1513}, 1543, 1553, 1601,... \\ 11 & \textbf{2329}, 2657, 2741, 2789, 2819, \textbf{2827}, \textbf{2839}, 2879, \textbf{3043}, 3089, \textbf{3151}, \textbf{3179}, 3203, \textbf{3205},... \\ 12 & \textbf{4369}, \textbf{4913}, 5441, 5483, \textbf{5485}, \textbf{5617}, 5639, \textbf{5911}, \textbf{6001}, 6029, 6053, \textbf{6103}, 6173, 6257,... \\ \hline \end {tabular} } \caption {Numbers in Section I of Classes 0 to 12} \label {Ta3} \end {center} \end {table} Shapiro, observing that the smallest number in each of the classes 1 through 8 is prime, conjectured that the smallest number is prime for all classes. However, Mills~\cite {Mills} found counterexamples. Later, Catlin~\cite [Theorem 1] {Catlin} proved that if the smallest number in a class is odd, then it can be factored into the product of other such numbers. For example, the smallest numbers in classes 11 and 12 factor as $2329=17 \cdot 137$ and $4369=17 \cdot 257$; note that 17, 137, and 257 are the smallest numbers in classes 4, 7, and 8, respectively. \section {Theorems about primes in classes} Although Shapiro and Catlin give a nice characterization of the composite section~I numbers, their papers say little about the prime numbers in sections~I and~II. We prove five theorems about those primes. \begin {theorem} \label {T.section-I} %-------------------------------------------------------------------------- theorem 1 Suppose $p$ is an odd prime and $p=1+2^k m$, with $k>0$ and $m$ odd. Then $p$ is in section~I of its class if and only if $m$ is in section~I of its class. \end {theorem} \begin {proof} Observe that for prime $p$, $\phi(p)=p-1$, and hence, $C(p-1)=C(p)-1$. From Shapiro's properties of the $C$ function, we have $C(p-1) = k-1 + C(m)$. Therefore, $C(p) = C(m) + k$. For a prime $p$ in section~I, we have the inequality \begin {equation*} 2^{C(p)} < p < 2^{C(p)+1}. \end {equation*} Substituting $p=1+2^k m$, we obtain \begin {equation*} 2^{C(m)+k} < 1+2^k m < 2^{C(m)+k+1}. \end {equation*} Dividing by $2^k$ produces the inequality \begin {equation*} 2^{C(m)} < m < 2^{C(m)+1}, \end {equation*} showing that $m$ is a number in section~I of its class, which is $C(p)-k$. The proof in the other direction is just as easy. For a number $m$ in section~I, we have the inequality \begin {equation*} 2^{C(m)} < m < 2^{C(m)+1}. \end {equation*} Multiplying by $2^k$ produces the inequality \begin {equation*} 2^{C(m)+k} < 2^k m < 2^{C(m)+k+1}. \end {equation*} Adding 1 to $2^k m$ does not change the inequality because there is always an odd number between two evens. Hence, we obtain \begin {equation*} 2^{C(m)+k} < 1+2^k m < 2^{C(m)+k+1}. \end {equation*} But, for integers, this inequality is the same as \begin {equation*} 2^{C(p)} < p < 2^{C(p)+1}, \end {equation*} which means $p$ is in section~I of its class, which is $C(m)+k$. \end {proof} \begin {theorem} \label {T.section-II} %-------------------------------------------------------------------------- theorem 2 Suppose $p$ is an odd prime and $p=1+2^k m$, with $k>0$ and $m$ odd. Then $p$ is in section~II of its class if and only if $m$ is in section~II of its class. \end {theorem} \begin {proof} Negating Theorem~\ref {T.section-I}, we have that $p$ is not in Section~I if and only if $m$ is not in section~I. Because section~III consists of only even numbers greater than 2, a prime (and an odd number) not in section~I must be in section~II. Hence, the theorem follows. \end {proof} \begin {theorem} \label {T.factors} %-------------------------------------------------------------------------- theorem 3 If prime $p$ is in section~I of a class, then the factors of $p-1$ are 2 and primes in section~I of their class. \end {theorem} \begin {proof} Factor $p-1$ into the product of an even number and an odd number: $p-1 = 2^k m$, where $m$ is an odd number and $k>0$. By Theorem~\ref {T.section-I}, $m$ is a number in section~I of its class. Using Shapiro's Property~11, we conclude that the prime factors of $m$ are all in section~I of their class. Clearly, 2 is also a factor of $p-1$, proving the theorem. \end {proof} \begin {theorem} \label {T.prime} %-------------------------------------------------------------------------- theorem 4 If the smallest number in a class is odd prime $p$, then the prime factors of $p-1$ are 2 and primes that are the smallest numbers in their class. \end {theorem} \begin {proof} From properties of the $C$ function, we know that the smallest number in class~$n$ is either~$2^{n+1}$ or a number in section~I of the class. By assumption, the smallest number is prime. Hence, the prime $p$ must be in section~I. By Theorem~\ref {T.section-I}, if~$p$ is a prime in section~I and $p=1+2^k m$, with $k>0$ and~$m$ odd, then~$m$ is a number in section~I of its class. Let~$q$ be a prime factor of~$m$. Then we can write $m= q \, s$ and $$p = 1 + 2^k ~ q \, s$$ $$C(p) = k + C(q)+C(s).$$ Because~$m$ is in section~I, by Property~11,~$q$ is also. The prime~$q$ must be the least number in its class, otherwise if there is a smaller number,~$p$ would be smaller (but in the same class), which would contradict the assumption that~$p$ is the smallest number in its class. It is obvious that 2 is a prime factor of $p-1$. \end {proof} Combining this result with Catlin's theorem, the next theorem gives us a more complete description of the smallest number in a class. \begin {theorem} \label {T.combined} %------------------------------------------------------------------ theorem 5 Suppose that the smallest number $x$ in a class is odd. If $x$ is composite, then its prime factors are the smallest numbers in their respective classes. If~$x$ is prime, then the prime factors of $x-1$ are~2 and primes that are the smallest numbers in their respective classes. \end {theorem} \begin {proof} The composite case is implied by Catlin's theorem. The prime case is Theorem~\ref {T.prime}. \end {proof} \section {A multiplicative function} For more insight into the odd numbers in sections I and II, it is useful to introduce the function $$D(x)=\frac {x} {2^{C(x)}}$$ for odd integers $x$. (Here, D could mean ``depth''; we want low values of D.) Using Property~1, it is easy to show that $D$ is completely multiplicative; that is, for odd integers $x$ and $y$, $$D(x y)=D(x) D(y).$$ Observe that $D(x) < 2$ if and only if $x$ is in section~I of its class. If we write a prime number $p=1+2^k m$ with $m$ odd, then it is easy to show that $$D(p)=2^{-C(p)}+D(m).$$ Hence, if $D(m)$ is very small, then $D(p)$ will be small. Clearly $D(1)=1$ is the smallest value of the $D$ function. If $F_5=2^{16}+1=65537$ is the largest Fermat prime, then $D(F_5)$ is the second-lowest value of the $D$ function. This value is so low that the first $45426=\lfloor (\log 2)/(\log D(F_5)) \rfloor$ powers of $F_5$ are also section~I numbers! \section {Computing the least number in a class} Let $c_n$ be the least number in class $n$. For $n=1, 2, 3,\ldots, 16, c_n$ is $$3, 5, 11, 17, 41, 83, 137, 257, 641, 1097, 2329, 4369, 10537, 17477, 35209, 65537,$$ which is sequence \seqnum{A007755}. When computing $c_n$, there are two cases to consider: whether $c_n$ is composite or prime. As mentioned above, Catlin proves that when $c_n$ is composite, its factors are among the $c_k$ for $k