On Perfect Totient Numbers

Douglas E. Iannucci University of the Virgin Islands St Thomas, VI 00802 USA

                    diannuc@uvi.edu

Deng Moujie Science and Engineering College Hainan University Haikou City 570228 P. R. China

                  dmj2002@hotmail.com

Graeme L. Cohen University of Technology, Sydney PO Box 123, Broadway NSW 2007 Australia

                Graeme.Cohen@uts.edu.au

Abstract

Let n > 2 be a positive integer and let ϕ denote Euler’s totient function. Define ϕ^{1}(n) = ϕ(n) and ϕ^{k}(n) = ϕ(ϕ^{k−1}(n)) for all integers k ≥ 2. Define the arithmetic function S by S(n) = ϕ(n) + ϕ^{2}(n) + ⋯ + ϕ^{c}(n) + 1, where ϕ^{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.

1 Introduction

Let n > 2 be a positive integer and let ϕ denote Euler’s totient function. Define ϕ^{1}(n) = ϕ(n) and ϕ^{k}(n) = ϕ(ϕ^{k−1}(n)) for all integers k ≥ 2. Shapiro [4] defines the class number C(n) of n by that integer c such that ϕ^{c}(n) = 2. Define the arithmetic function S by

S(n) = ϕ(n) + ϕ^{2}(n) + ⋯ + ϕ^{c}(n) + 1,

where c = C(n). Note that ϕ^{c+1}(n) = 1. We say that n is a perfect totient number (or PTN for short) if S(n) = n.

Since ϕ(n) is even if ϕ(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 · 10^{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 [5]: If p = 2^{2}3^{b} + 1 is prime then 3p is a PTN. A search of b ≤ 5000, beyond those giving entries in Table 1, turned up the following nine values for which p = 2^{2}3^{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 [3]).

15 = 3 · 5  36759 = 3 · 12253
39 = 3 · 13  46791 = 3^{3} · 1733
111 = 3 · 37  65535 = 3 · 5 · 17 · 257
183 = 3 · 61  140103 = 3^{3} · 5189
255 = 3 · 5 · 17  208191 = 3 · 29 · 239
327 = 3 · 109  441027 = 3^{2} · 49003
363 = 3 · 11^{2}  4190263 = 7 · 11 · 54419
471 = 3 · 157  9056583 = 3^{3} · 335429
2199 = 3 · 733  57395631 = 3 · 19131877
3063 = 3 · 1021  172186887 = 3 · 57395629
4359 = 3 · 1453  236923383 = 3 · 1427 · 55343
4375 = 5^{4} · 7  918330183 = 3^{3} · 34012229
5571 = 3^{2} · 619  3932935775 = 5^{2} · 29 · 5424739
8751 = 3 · 2917  4294967295 = 3 · 5 · 17 · 257 · 65537
15723 = 3^{2} · 1747  4764161215 = 5 · 11 · 86621113

Table 1: PTNs less than 5 · 10^{9} (except powers of 3).

The study of PTNs was initiated by Perez Cacho [2] 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 [1] proved that 3p, for an odd prime p, is not a PTN if p ≡ 3 (mod 4). 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 → 39 → 471, 3^{2} → 111, 15 → 183 → 2199, 3^{3} → 327, 255 → 3063 → 36759, 363 → 4359, 3^{6} → 8751, 3^{14} → 57395631, 3^{15} → 172186887.

The purpose of this paper is to investigate PTNs of the form 3^{k}p, for k ≥ 2 and p prime. As an aside we note a curious result: the fact that ϕ(n) ≤ n/2 when n is even easily

implies that ϕ(n) > n/2 when n is a PTN.

2 Sufficient Conditions for PTNs

Mohan and Suryanarayana found sufficient conditions on an odd prime p for 3^{2}p and 3^{3}p 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^{5}3^{b} + 1 and p = 2 · 3^{2}q + 1 are both prime then 3^{2}p is a PTN, and if q = 2^{4}3^{b} + 1 and p = 2^{2}q + 1 are both prime then 3^{3}p is a PTN. There is one known example of their Theorem 5, that being the PTN 15723 = 3^{2}1747 which occurs when b = 1. Their Theorem 6 has three known examples: the PTNs 46791 = 3^{3}1733 (b = 3), 140103 = 3^{3}5189 (b = 4), and 918330183 = 3^{3} · 34012229 (b = 12). The values b ≤ 5000 (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^{2}p to be a PTN (three of which are given in the following Theorem), and two sufficient conditions for 3^{3}p to be a PTN.

Theorem 1 Let b be a nonnegative integer. If r, q, and p, as given, are all prime then 3^{2}p is a PTN:

1. r = 2^{4}3^{b} + 1, q = 2 · 3r + 1, and p = 2 · 3q + 1;

2. r = 2 · 3^{b} + 1, q = 2^{3}r + 1, and p = 2q + 1;

3. r = 2^{2}3^{b} + 1, q = 2^{3}3r + 1, and p = 2q + 1.

Proof: (Part 1) We have 3^{2}p = 2^{6}3^{b+4} + 387 by direct substitution. Also,

S(3^{2}p) = 2^{2}3^{2}q + 2^{3}3^{2}r + 2^{7}3^{b+1} + 2^{7}3^{b} + ⋯ + 2^{7} + 2^{6} + ⋯ + 1
= 2^{7}(3^{b+3} + ⋯ + 3 + 1) + 451
= 2^{6}3^{b+4} + 387 .

The proofs of Parts 2 and 3 are similar. □

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 ≤ 3000. In Parts 2 and 3, no examples occur for b ≤ 3000.

Theorem 2 Let b be a nonnegative integer. If q = 2^{3}3^{b} + 1 and p = 2q + 1 are both prime, then 3^{2}p is a PTN.

Theorem 3 Let b be a nonnegative integer. If r = 2^{2}3^{b} + 1, q = 2^{4}r + 1, and p = 2^{2}q + 1 are all prime, then 3^{3}p is a PTN.

Theorem 4 Let b be a nonnegative integer. If s = 2^{5}3^{b} + 1, r = 2 · 3^{2}s + 1, q = 2^{4}3r + 1, and p = 2^{2}q + 1 are all prime, then 3^{3}p is a PTN.

Direct proofs of Theorems 2–4 may be obtained as above. In Theorem 2, examples do not occur for b ≤ 5000, and in Theorem 3, examples do not occur for b ≤ 3000. 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 ≤ 2000.

3 PTNs of the form 3^{k}p

In seeking examples of PTNs of the form 3^{k}p, k ≥ 2, we considered primes p and q such that q = 2^{a}3^{b} + 1 and p = 2^{c}3^{d}q + 1, where a, c ≥ 1 and b, d ≥ 0. Direct substitution gives

3^{k}p = 2^{a+c}3^{b+d+k} + 2^{c}3^{d+k} + 3^{k} .

On the other hand, we have

S(3^{k}p) = 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} + ⋯
+ 2^{a+c+1} + ⋯ + 1
= 2^{c+1}3^{d+k−1} + 2^{a+c+1}(3^{b+d+k−1} + ⋯ + 3 + 1) + 2^{a+c} + ⋯ + 1
= 2^{c+1}3^{d+k−1} + 2^{a+c}3^{b+d+k} + 2^{a+c} − 1.

Assuming 3^{k}p is a PTN, we equate the above expressions for 3^{k}p and S(3^{k}p) and simplify to obtain the diophantine equation

2^{c}(2^{a} − 3^{d+k−1}) = 3^{k} + 1.  (1)

Clearly, a > 1 and c = 1 or 2 for k even or odd, respectively.

When k = 2, the right-hand side of (1) is 10; thus c = 1 and the equation reduces to

2^{a} − 3^{d+1} = 5.  (2)

Since 2^{a} ≡ 2 (mod 3), 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} ≡ 123 (mod 128), which implies d + 1 ≡ 11 (mod 32). This in turn implies 3^{d+1} ≡ 7 (mod 17), and thus 2^{a} ≡ 7 + 5 ≡ 12 (mod 17), which is impossible. Thus the only solutions to (2) 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 [1].

When k = 3, (1) reduces to

2^{a} − 3^{d+2} = 7.  (3)

Clearly a ≥ 3. Since 2^{a} ≡ 1 (mod 3) and 3^{d+2} ≡ 1 (mod 8), we must have a and d both even. Write a = 2α and d = 2δ. Then (3) reduces to

(2^{α} + 3^{δ+1})(2^{α} − 3^{δ+1}) = 7.  (4)

Therefore 2^{α} − 3^{δ+1} = 1 and 2^{α} + 3^{δ+1} = 7, implying α = 2, δ = 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 [1].

We show next that there are no solutions of (1) when k ≥ 4.

Suppose first that k is even, k ≥ 4. Then c = 1. Put x = a + 1 and y = d + k − 1 so that (1) may be given as

2^{x} − 2 · 3^{y} = 3^{k} + 1,  (5)

where x ≥ 3, y ≥ 3. Then 2^{x} ≡ 1 (mod 27), from which x ≡ 0 (mod 18). Since 2^{18} ≡ 1 (mod 19), we then have −2 · 3^{y} ≡ 3^{k} (mod 19), so that

(\frac{3}{19})^{y} = (\frac{−2 · 3^{y}}{19} ) = (\frac{3^{k}}{19}) = (\frac{3}{19})^{k} ,

where (\frac{·}{·}) is a Legendre symbol. Also, from (5), −2 · 3^{y} ≡ 3^{k} + 1 ≡ 2 (mod 8), 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 ≥ 5. Then c = 2. Put x = a + 2 and y = d + k − 1 so that (1) becomes

2^{x} − 4 · 3^{y} = 3^{k} + 1,  (6)

where x ≥ 4, y ≥ 4. There are two main cases to consider.

(a) If k ≡ 1 (mod 4), then −4 · 3^{y} ≡ 3^{k} + 1 ≡ 4 (mod 16), implying that y is odd. Also, as immediately above, x ≡ 0 (mod 18). Since 2^{18} ≡ 1 (mod 7), then −4 · 3^{y} ≡ 3^{k} (mod 7), so 3^{y+1} ≡ 3^{k} (mod 7). This is impossible when y + 1 is even and k is odd.

(b) If k ≡ 3 (mod 4), then −4 · 3^{y} ≡ 3^{k} + 1 ≡ 12 (mod 16), so y is even. Suppose first that y ≡ 0 (mod 4). Then 2^{x} ≡ 4 · 3^{y} + 3^{k} + 1 ≡ 4 + 2 + 1 ≡ 2 (mod 5). This implies that x is odd. But, from (6), 2^{x} ≡ 1 (mod 3), so x is even. We have a contradiction.

The most difficult case to eliminate is when k ≡ 3 (mod 4) and y ≡ 2 (mod 4). Consideration of (6), modulo 5, implies 2^{x} ≡ 4 (mod 5), so x ≡ 2 (mod 4). From (6), we also have 2^{x} ≡ 1 (mod 27), so x ≡ 0 (mod 18) and then, since x ≡ 2 (mod 4), we have x ≡ 18 (mod 36). This then implies that 2^{x} ≡ −1 (mod 13). Consideration of the nine possibilities that arise from (6), modulo 13, taking y ≡ 2, 6 or 10 (mod 12) and k ≡ 3, 7 or 11 (mod 12) shows that in fact y ≡ 2 (mod 12) and k ≡ 3 (mod 12). Now consider a further nine cases of (6), modulo 37, taking y ≡ 2, 14 or 26 (mod 36) and k ≡ 3, 15 or 27 (mod 36). The only possibility is y ≡ 2 (mod 36) and k ≡ 27 (mod 36). But in that case, since 2^{18} ≡ 3^{36} ≡ 1 (mod 73), we find that 2^{x} − 4 · 3^{y} ≡ 1 − 4 · 9 ≡ 38 (mod 73) and 3^{k} + 1 ≡ 27 + 1 = 28 (mod 73). This contradicts (6).

We give this conclusion as:

Theorem 5 There are no PTNs of the form 3^{k}p, k ≥ 4, where p = 2^{c}3^{d}q+1 and q = 2^{a}3^{b}+1 are primes with a, c ≥ 1 and b, d ≥ 0.

We next considered another possibility: let a, c, e ≥ 1 and b, d, f ≥ 0 be integers. Suppose r = 2^{a}3^{b} + 1, q = 2^{c}3^{d}r + 1, and p = 2^{e}3^{f}q + 1 are all prime, and let n = 3^{k}p for k ≥ 2.

Substitution gives us

n = 2^{a+c+e}3^{b+d+f+k} + 2^{c+e}3^{d+f+k} + 2^{e}3^{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

2^{e}(2^{c}(2^{a} − 3^{d+f+k−2}) − 3^{f+k−1}) = 3^{k} + 1 .  (7)

We found four solutions to (7), with a, c, d, f ≤ 20 and k ≤ 10. 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 ≥ 1, b, d, f, h ≥ 0, where all of s = 2^{a}3^{b} +1, r = 2^{c}3^{d}s + 1, q = 2^{e}3^{f}r + 1, and p = 2^{g}3^{h}q + 1 are supposed prime. Then, as above, letting n = 3^{k}p for k ≥ 3 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^{k}p for k ≥ 4.

References

[1] A. L. Mohan and D. Suryanarayana, “Perfect totient numbers”, in: Number Theory (Proc. Third Matscience Conf., Mysore, 1981) Lect. Notes in Math. 938, Springer-Verlag, New York, 1982, pp. 101–105.

[2] L. Perez Cacho, Sobre la suma de indicadores de ordenes sucesivos, Revista Matematica Hispano-Americana 5.3 (1939), 45–50.

[3] H. Riesel, Prime Numbers and Computer Methods for Factorization, 2nd edition, Birkhäuser, Boston, 1994.

[4] H. Shapiro, An arithmetic function arising from the ϕ function, Amer. Math. Monthly 50 (1943), 18–30.

[5] T. Venkataraman, Perfect totient number, Math. Student 43 (1975), 178.

2000 Mathematics Subject Classification: Primary 11A25. Keywords: totient, perfect totient number, class number, diophantine equation.

Received July 23 2003; revised version received October 2 2003. Published in Journal of Integer Sequences, December 18 2003. Minor typo corrected, June 8 2009.

Return to Journal of Integer Sequences home page.