\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{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 Perfect Totient Numbers } \vskip 1cm {\large Douglas E. Iannucci\\ University of the Virgin Islands\\ St Thomas, VI 00802\\ USA\\ \href{mailto:diannuc@uvi.edu}{\tt diannuc@uvi.edu} \\ \vskip .2in Deng Moujie\\ Science and Engineering College\\ Hainan University\\ Haikou City 570228\\ P. R. China\\ \href{mailto:dmj2002@hotmail.com}{\tt dmj2002@hotmail.com} \\ \vskip .2in Graeme L. Cohen\\ University of Technology, Sydney\\ PO Box 123, Broadway\\ NSW 2007\\ Australia\\ \href{mailto:Graeme.Cohen@uts.edu.au}{\tt Graeme.Cohen@uts.edu.au} \\ } \end{center} \vskip .2 in \begin{abstract} Let $n>2$ be a positive integer and let $\phi$ denote Euler's totient function. Define $\phi^1(n)=\phi(n)$ and $\phi^k(n)=\phi(\phi^{k-1}(n))$ for all integers $k\ge2$. Define the arithmetic function $S$ by $S(n)=\phi(n)+\phi^2(n)+\cdots+\phi^c(n)+1$, where $\phi^c(n)=2$. We say $n$ is a perfect totient number if $S(n)=n$. We give a list of known perfect totient numbers, and we give sufficient conditions for the existence of further perfect totient numbers. \end{abstract} \newtheorem{theorem}{\sc Theorem} \section{Introduction} Let $n>2$ be a positive integer and let $\phi$ denote Euler's totient function. Define $\phi^1(n)=\phi(n)$ and $\phi^k(n)=\phi(\phi^{k-1}(n))$ for all integers $k\ge2$. Shapiro~\cite{shapiro} defines the {\it class number\/} $C(n)$ of $n$ by that integer $c$ such that $\phi^c(n)=2$. Define the arithmetic function $S$ by \[ S(n)=\phi(n)+\phi^2(n)+\cdots+\phi^c(n)+1, \] where $c=C(n)$. Note that $\phi^{c+1}(n)=1$. We say that $n$ is a {\it perfect totient number\/} (or PTN for short) if $S(n)=n$. Since $\phi(n)$ is even if $\phi(n)>1$, it follows that all PTNs are odd. It is easy to show that $3^k$ is a PTN for all positive integers $k$. In Table~1 the 30 PTNs less than $5\cdot10^9$ which are not powers of~3 are given. In addition to the PTNs given in Table~1, nine more were found by applying a result of Venkataraman~\cite{ven}: If $p=2^23^b+1$ is prime then $3p$ is a PTN. A search of $b\le5000$, beyond those giving entries in Table~1, turned up the following nine values for which $p=2^23^b+1$ is prime (and therefore $3p$ is a PTN): $b=39$, 201, 249, 885, 1005, 1254, 1635, 3306, 3522. The PTN which corresponds to $b=3522$ has 1682 digits. Primality was verified with either UBASIC or Mathematica, by applying Lehmer's converse of Fermat's Theorem (Theorem~4.3 in Riesel~\cite{rie}). %\begin{table} %\caption{PTNs less than $5\cdot10^9$ (except powers of 3)} %\begin{align*} %15&=3\cdot5 \\ %39&=3\cdot13 \\ %111&=3\cdot37 \\ %183&=3\cdot61 \\ %255&=3\cdot5\cdot17 \\ %327&=3\cdot109 \\ %363&=3\cdot11^2 \\ %471&=3\cdot157 \\ %2199&=3\cdot733 \\ %3063&=3\cdot1021 \\ %4359&=3\cdot1453 \\ %4375&=5^4\cdot7 \\ %5571&=3^2\cdot619 \\ %8751&=3\cdot2917 \\ %15723&=3^2\cdot1747 \\ %36759&=3\cdot12253\\ %46791&=3^3\cdot1733\\ %65535&=3\cdot5\cdot17\cdot257\\ %140103&=3^3\cdot5189\\ %208191&=3\cdot29\cdot2393\\ %441027&=3^2\cdot49003\\ %4190263&=7\cdot11\cdot54419\\ %9056583&=3^3\cdot335429\\ %57395631&=3\cdot19131877\\ %172186887&=3\cdot57395629\\ %236923383&=3\cdot1427\cdot55343\\ %918330183&=3^3\cdot34012229\\ %3932935775&=5^2\cdot29\cdot5424739\\ %4294967295&=3\cdot5\cdot17\cdot257\cdot65537\\ %4764161215&=5\cdot11\cdot86621113 %\end{align*} %\end{table} \begin{xalignat*}{2} 15&=3\cdot5 & 36759&=3\cdot12253\\ 39&=3\cdot13 &46791&=3^3\cdot1733 \\ 111&=3\cdot37 & 65535&=3\cdot5\cdot17\cdot257 \\ 183&=3\cdot61 & 140103&=3^3\cdot5189\\ 255&=3\cdot5\cdot17 &208191&=3\cdot29\cdot239\\ 327&=3\cdot109& 441027&=3^2\cdot49003\\ 363&=3\cdot11^2& 4190263&=7\cdot11\cdot54419\\ 471&=3\cdot157 &9056583&=3^3\cdot335429\\ 2199&=3\cdot733 &57395631&=3\cdot19131877\\ 3063&=3\cdot1021 &172186887&=3\cdot57395629\\ 4359&=3\cdot1453 &236923383&=3\cdot1427\cdot55343\\ 4375&=5^4\cdot7 &918330183&=3^3\cdot34012229\\ 5571&=3^2\cdot619&3932935775&=5^2\cdot29\cdot5424739 \\ 8751&=3\cdot2917 &4294967295&=3\cdot5\cdot17\cdot257\cdot65537\\ 15723&=3^2\cdot1747& 4764161215&=5\cdot11\cdot86621113\\ \end{xalignat*} \vskip-.15in \centerline{Table 1: PTNs less than $5\cdot10^9$ (except powers of 3).} \bigskip The study of PTNs was initiated by Perez Cacho~\cite{cacho} when he proved that $3p$, for an odd prime $p$, is a PTN if and only if $p=4n+1$, where $n$ is a PTN. Note that Venkataraman's result, mentioned above, follows as a corollary. Mohan and Suryanarayana~\cite{ms} proved that $3p$, for an odd prime $p$, is not a PTN if $p\equiv3\pmod4$. Thus PTNs of the form $3p$ have been completely characterized. Applying Perez Cacho's result gives the following as the only known chains of PTNs, apart from the nine examples of length~2 mentioned earlier: $3\to39\to471$, $3^2\to111$, $15\to183\to2199$, $3^3\to327$, $255\to3063\to36759$, $363\to4359$, $3^6\to8751$, $3^{14}\to57395631$, $3^{15}\to172186887$. The purpose of this paper is to investigate PTNs of the form $3^kp$, for $k\ge2$ and $p$ prime. As an aside we note a curious result: the fact that $\phi(n) \leq n/2$ when $n$ is even easily implies that $\phi(n)>n/2$ when $n$ is a PTN. \section{Sufficient Conditions for PTNs} Mohan and Suryanarayana found sufficient conditions on an odd prime $p$ for $3^2p$ and $3^3p$ to be PTNs, given in their paper as Theorem~5 and Theorem~6. In particular, let $b$ be a nonnegative integer. Then, respectively, if $q=2^53^b+1$ and $p=2\cdot3^2q+1$ are both prime then $3^2p$ is a PTN, and if $q=2^43^b+1$ and $p=2^2q+1$ are both prime then $3^3p$ is a PTN. There is one known example of their Theorem~5, that being the PTN $15723=3^21747$ which occurs when $b=1$. Their Theorem~6 has three known examples: the PTNs $46791=3^31733$ ($b=3$), $140103=3^35189$ ($b=4$), and $918330183=3^3\cdot34012229$ ($b=12$). The values $b\le5000$ (for both theorems) were tested, but no further examples were found. Let $p$ be an odd prime. We have found four further sufficient conditions on $p$ for $3^2p$ to be a PTN (three of which are given in the following Theorem), and two sufficient conditions for $3^3p$ to be a PTN. \begin{theorem} Let $b$ be a nonnegative integer. If $r$, $q$, and $p$, as given, are all prime then $3^2p$ is a PTN: \begin{enumerate} \item $r=2^43^b+1$, $q=2\cdot3r+1$, and $p=2\cdot3q+1$; \item $r=2\cdot3^b+1$, $q=2^3r+1$, and $p=2q+1$; \item $r=2^23^b+1$, $q=2^33r+1$, and $p=2q+1$. \end{enumerate} \end{theorem} \noindent{\sc Proof:} (Part 1) We have $3^2p=2^63^{b+4}+387$ by direct substitution. Also, \begin{align*} S(3^2p)&=2^23^2q+2^33^2r+2^73^{b+1}+2^73^{b}+\cdots+2^7+2^6+\cdots+1\\ &=2^7(3^{b+3}+\cdots+3+1)+451\\ &=2^63^{b+4}+387\,. \end{align*} The proofs of Parts 2~and 3~are similar.\quad$\square$ In Part 1, when $b=0$, we have $r=17$, $q=103$, and $p=619$, giving the PTN 5571. There are no more examples for $b\le3000$. In Parts~2 and~3, no examples occur for $b\le3000$. \begin{theorem} Let $b$ be a nonnegative integer. If $q=2^33^b+1$ and $p=2q+1$ are both prime, then $3^2p$ is a PTN. \end{theorem} \begin{theorem} Let $b$ be a nonnegative integer. If $r=2^23^b+1$, $q=2^4r+1$, and $p=2^2q+1$ are all prime, then $3^3p$ is a PTN. \end{theorem} \begin{theorem} Let $b$ be a nonnegative integer. If $s=2^53^b+1$, $r=2\cdot3^2s+1$, $q=2^43r+1$, and $p=2^2q+1$ are all prime, then $3^3p$ is a PTN. \end{theorem} Direct proofs of Theorems 2--4 may be obtained as above. In Theorem~2, examples do not occur for $b\le5000$, and in Theorem~3, examples do not occur for $b\le3000$. In Theorem~4, when $b=1$, we have $s=97$, $r=1747$, $q=83857$, and $p=335429$, giving the PTN 9056583. There are no more examples for $b\le2000$. \section{PTNs of the form $3^kp$} In seeking examples of PTNs of the form $3^kp$, $k\ge2$, we considered primes $p$ and $q$ such that $q=2^a3^b+1$ and $p=2^c3^dq+1$, where $a$, $c\ge1$ and $b$, $d\ge0$. Direct substitution gives $$3^kp=2^{a+c}3^{b+d+k}+2^c3^{d+k}+3^k\,.$$ On the other hand, we have \begin{align*} S(3^kp)&=2^{c+1}3^{d+k-1}q+2^{a+c+1}3^{b+d+k-2}+2^{a+c+1}3^{b+d+k-3}+\dotsb\\ &\phantom{={}}{}+2^{a+c+1}+\dots+1\\ &=2^{c+1}3^{d+k-1}+2^{a+c+1}(3^{b+d+k-1}+\cdots+3+1)+2^{a+c}+\dots+1\\ &=2^{c+1}3^{d+k-1}+2^{a+c}3^{b+d+k}+2^{a+c}-1. \end{align*} Assuming $3^kp$ is a PTN, we equate the above expressions for $3^kp$ and $S(3^kp)$ and simplify to obtain the diophantine equation \begin{equation}\label{pq} 2^c(2^a-3^{d+k-1})=3^k+1. \end{equation} Clearly, $a>1$ and $c=1$ or 2 for $k$ even or odd, respectively. When $k=2$, the right-hand side of (\ref{pq}) is 10; thus $c=1$ and the equation reduces to \begin{equation}\label{pqk2} 2^a-3^{d+1}=5. \end{equation} Since $2^a\equiv2\pmod3$, we must have $a$ odd. We have $a=3$, $d=0$ as one solution, and we have $a=5$, $d=2$ as another. If $a>5$ then $3^{d+1}\equiv123\pmod{128}$, which implies $d+1\equiv11\pmod{32}$. This in turn implies $3^{d+1}\equiv7\pmod{17}$, and thus $2^a\equiv7+5\equiv12\pmod{17}$, which is impossible. Thus the only solutions to (\ref{pqk2}) are given by $a=3$, $d=0$, and by $a=5$, $d=2$. Since also $c=1$, this statement includes both our Theorem~2 and Theorem~5 of Mohan and Suryanarayana~\cite{ms}. When $k=3$, (\ref{pq}) reduces to \begin{equation}\label{pqk3} 2^a-3^{d+2}=7. \end{equation} Clearly $a\ge3$. Since $2^a\equiv1\pmod3$ and $3^{d+2}\equiv1\pmod8$, we must have $a$ and $d$ both even. Write $a=2\alpha$ and $d=2\delta$. Then (\ref{pqk3}) reduces to \begin{equation}\label{pqk3a} (2^{\alpha}+3^{\delta+1})(2^{\alpha}-3^{\delta+1})=7. \end{equation} Therefore $2^{\alpha}-3^{\delta+1}=1$ and $2^{\alpha}+3^{\delta+1}=7$, implying $\alpha=2$, $\delta=0$, which in turn implies $a=4$, $d=0$ as the only solution. Together with $c=2$, this includes the statement of Theorem 6 in Mohan and Suryanarayana~\cite{ms}. We show next that there are no solutions of (\ref{pq}) when $k\ge4$. Suppose first that $k$ is even, $k\ge4$. Then $c=1$. Put $x=a+1$ and $y=d+k-1$ so that (\ref{pq}) may be given as \begin{equation}\label{pqk4even} 2^x-2\cdot3^y=3^k+1, \end{equation} where $x\ge3$, $y\ge3$. Then $2^x\equiv1\pmod{27}$, from which $x\equiv0\pmod{18}$. Since $2^{18}\equiv1\pmod{19}$, we then have $-2\cdot3^y\equiv3^k\pmod{19}$, so that \[ \left(\frac3{19}\right)^y=\left(\frac{-2\cdot3^y}{19}\right)=\left(\frac{3^k}{19}\right) =\left(\frac3{19}\right)^k, \] where $\left(\frac\cdot\cdot\right)$ is a Legendre symbol. Also, from (\ref{pqk4even}), $-2\cdot3^y\equiv3^k+1\equiv2\pmod8$, so $y$ is odd. Then we have a contradiction since $k$ is even, $y$ is odd, and the Legendre symbol $(3/19)=-1$. Suppose next that $k$ is odd, $k\ge5$. Then $c=2$. Put $x=a+2$ and $y=d+k-1$ so that (\ref{pq}) becomes \begin{equation}\label{pqk4odd} 2^x-4\cdot3^y=3^k+1, \end{equation} where $x\ge4$, $y\ge4$. There are two main cases to consider. (a) If $k\equiv1\pmod4$, then $-4\cdot3^y\equiv3^k+1\equiv4\pmod{16}$, implying that $y$ is odd. Also, as immediately above, $x\equiv0\pmod{18}$. Since $2^{18}\equiv1\pmod7$, then $-4\cdot3^y\equiv3^k\pmod7$, so $3^{y+1}\equiv3^k\pmod7$. This is impossible when $y+1$ is even and $k$ is odd. (b) If $k\equiv3\pmod4$, then $-4\cdot3^y\equiv3^k+1\equiv12\pmod{16}$, so $y$ is even. Suppose first that $y\equiv0\pmod4$. Then $2^x\equiv4\cdot3^y+3^k+1\equiv4+2+1\equiv2\pmod5$. This implies that $x$ is odd. But, from (\ref{pqk4odd}), $2^x\equiv1\pmod3$, so $x$ is even. We have a contradiction. The most difficult case to eliminate is when $k\equiv3\pmod4$ and $y\equiv2\pmod4$. Consideration of (\ref{pqk4odd}), modulo 5, implies $2^x\equiv4\pmod5$, so $x\equiv2\pmod4$. From (\ref{pqk4odd}), we also have $2^x\equiv1\pmod{27}$, so $x\equiv0\pmod{18}$ and then, since $x\equiv2\pmod4$, we have $x\equiv18\pmod{36}$. This then implies that $2^x\equiv-1\pmod{13}$. Consideration of the nine possibilities that arise from (\ref{pqk4odd}), modulo 13, taking $y\equiv2$, 6 or $10\pmod{12}$ and $k\equiv3$, 7 or $11\pmod{12}$ shows that in fact $y\equiv2\pmod{12}$ and $k\equiv3\pmod{12}$. Now consider a further nine cases of (\ref{pqk4odd}), modulo 37, taking $y\equiv2$, 14 or $26\pmod{36}$ and $k\equiv3$, 15 or $27\pmod{36}$. The only possibility is $y\equiv2\pmod{36}$ and $k\equiv27\pmod{36}$. But in that case, since $2^{18}\equiv3^{36}\equiv1\pmod{73}$, we find that $2^x-4\cdot3^y\equiv1-4\cdot9\equiv38\pmod{73}$ and $3^k+1\equiv27+1=28\pmod{73}$. This contradicts (\ref{pqk4odd}). We give this conclusion as: \begin{theorem} There are no PTNs of the form $3^kp$, $k\ge4$, where $p=2^c3^dq+1$ and $q=2^a3^b+1$ are primes with $a$, $c\ge1$ and $b$, $d\ge0$. \end{theorem} We next considered another possibility: let $a$, $c$, $e\ge1$ and $b$, $d$, $f\ge0$ be integers. Suppose $r=2^a3^b+1$, $q=2^c3^dr+1$, and $p=2^e3^fq+1$ are all prime, and let $n=3^kp$ for $k\ge2$. Substitution gives us \[ n=2^{a+c+e}3^{b+d+f+k}+2^{c+e}3^{d+f+k}+2^e3^{f+k}+3^k, \] whereas substitution and calculation gives us \[ S(n)=2^{c+e+3}3^{d+f+k-2}+2^{e+1}3^{f+k-1}+2^{a+c+e}3^{b+d+f+k}+2^{a+c+e}-1. \] Assuming $n$ is a PTN, we equate the expressions for $n$ and $S(n)$ and simplify to obtain the diophantine equation \begin{equation}\label{pqr} 2^e(2^c(2^a-3^{d+f+k-2})-3^{f+k-1})=3^k+1\,. \end{equation} We found four solutions to (\ref{pqr}), with $a,c,d,f\le20$ and $k\le10$. Notice that $e=1$ or 2 if $k$ is even or odd respectively. Our first solution is given by $a=e=2$, $c=4$, $d=f=0$, and $k=3$. Note that this is Theorem~3. The second solution is given by $a=4$, $c=d=e=f=1$, and $k=2$. This is Part 1 of Theorem~1. The third solution is given by $a=e=1$, $c=3$, $d=f=0$, and $k=2$ (Part 2 of Theorem 1), and the fourth is given by $a=2$, $c=3$, $d=e=1$, $f=0$, and $k=2$ (Part 3 of Theorem 1). Similarly, we also considered integers $a,c,e,g\ge1$, $b,d,f,h\ge0$, where all of $s=2^a3^b+1$, $r=2^c3^ds+1$, $q=2^e3^fr+1$, and $p=2^g3^hq+1$ are supposed prime. Then, as above, letting $n=3^kp$ for $k\ge3$ and supposing $S(n)=n$ implies the diophantine equation \[ 2^g(2^e(2^c(2^a-3^{d+f+h+k-3})-3^{f+h+k-2})-3^{h+k-1})=3^k+1. \] We found several solutions, but only one of them produced any PTNs: $a=5$, $c=f=1$, $d=g=2$, $e=4$, $h=0$, and $k=3$. This is Theorem~4, which we have already seen produces one known PTN. The question remains open as to whether or not any PTNs exist of the form $3^kp$ for $k\ge4$. \begin{thebibliography}{9} \bibitem{ms} A. L. Mohan and D. Suryanarayana, ``Perfect totient numbers'', in: \emph{Number Theory (Proc. Third Matscience Conf., Mysore, 1981)} Lect. Notes in Math. \textbf{938}, Springer-Verlag, New York, 1982, pp.\ 101--105. \bibitem{cacho} L. Perez Cacho, Sobre la suma de indicadores de ordenes sucesivos, \emph{Revista Matematica Hispano-Americana} \textbf{5.3} (1939), 45--50. \bibitem{rie} H. Riesel, \emph{Prime Numbers and Computer Methods for Factorization}, 2nd edition, Birkh\"auser, Boston, 1994. \bibitem{shapiro} H. Shapiro, An arithmetic function arising from the $\phi$ function, \emph{Amer. Math. Monthly} \textbf{50} (1943), 18--30. \bibitem{ven} T. Venkataraman, Perfect totient number, \emph{Math. Student} \textbf{43} (1975), 178. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 11A25. \noindent \emph{Keywords:} totient, perfect totient number, class number, diophantine equation. \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received July 23 2003; revised version received October 2 2003. Published in {\it Journal of Integer Sequences}, December 18 2003. Minor typo corrected, June 8 2009. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}. \vskip .1in \end{document} \end{document}