On the Equation σ(n) = n + ϕ(n)

Douglas E. Iannucci Towers Condominiums B-16 3600 Contant St. Thomas, VI 00802 USA

                       diannuc@gmail.com

Abstract

In this paper we consider the equation σ(n) = n + ϕ(n), for which n = 2 is the only known solution. We provide necessary conditions for the existence of any larger solutions.

1 Introduction

Let σ(n) denote the sum of the (positive) divisors of n, and let ϕ(n) denote Euler’s phi function (the number of positive integers ≤ n and relatively prime to it). We remark that n = 2 is a solution to the equation

σ(n) = n + ϕ(n)  (1)

over natural numbers n. By Hardy and Wright [3, Thm. 324], the average value of σ(n) is \frac{1}{6}π^{2}n. By [3, Thm. 330], the average value of n+ϕ(n) is (π^{2} +6)n/π^{2}. Since \frac{1}{6}π^{2} ≈ 1.645 and (π^{2}+6)/π^{2} ≈ 1.608, it is quite natural to ask if (1) has any solutions n > 2. None are known, and the literature seems devoid of any mention to this specific problem. Other, similar problems have been discussed in publications such as Guy [2]; e.g., §B-38, ϕ(m) = σ(n), and §B-42, ϕ(σ(n)) = σ(ϕ(n)), ϕ(σ(n)) = n, ϕ(σ(n)) = ϕ(n). Some such problems have been solved and are popular topics of discussion on many internet forums; e.g., σ(n) + ϕ(n) = 2n if and only if n is a prime or n = 1. There are three sequences in OEIS (Sloane [5]) related to (1); e.g., \underline{A070159} (all n such that σ(n) − n divides ϕ(n)). In fact, all solutions n > 2 to (1), if they exist, would belong to sequence \underline{A055940}, which gives composite n such that σ(n) − n divides ϕ(n). For, when p is prime then ϕ(p)/(σ(p) − p) = p − 1, hence 2 is the only prime solution to (1). Thus we seek those members n of \underline{A055940} where the ratio ϕ(n)/(σ(n) − n)) = 1; none are known. A similar comment applies to \underline{A066679}, giving n such that σ(n) − n is divisible by ϕ(n): all members less than 10^{11} are given, the only one of which giving the ratio (σ(n) − n)/ϕ(n) = 1 being n = 2. Are there any more?

We conjecture that n = 2 is the only solution to (1), and in this paper we obtain necessary conditions for a solution n > 2 to exist.

2 Preliminaries

Dividing both sides of (1) by n yields

\frac{σ(n)}{n} = 1 + \frac{ϕ(n)}{n}.  (2)

The function σ(n)/n is multiplicative. For all primes p and natural numbers a,

\frac{σ(p^{a})}{p^{a}} = 1 + \frac{1}{p} + \frac{1}{p^{2}} + ⋯ + \frac{1}{p^{a}}  (3)

is monotonically increasing with a; hence taking the limit of the right hand side of (3) as a → ∞ yields

\frac{σ(p^{a})}{p^{a}} < \frac{p}{p − 1}.  (4)

If p < q are primes then q/(q − 1) ≤ (p + 1)/p, thus by (3) and (4),

\frac{σ(q^{b})}{q^{b}} < \frac{σ(p^{a})}{p^{a}}  (5)

for all natural numbers a, b. As well,

\frac{q^{b}}{ϕ(q^{b})} = \frac{q}{q − 1} < \frac{p}{p − 1} = \frac{p^{a}}{ϕ(p^{a})}  (6)

for all natural numbers a, b. By (4) we have

\frac{σ(n)}{n} < ∏_{p|n} \frac{p}{p − 1} = \frac{n}{ϕ(n)}.  (7)

As usual we let α = \frac{1}{2}(1+\sqrt{5}), the golden ratio. Immediately we obtain the following results.

Theorem 1. If n is a solution to (1) then

\frac{σ(n)}{n} < α < \frac{n}{ϕ(n)}.

Proof. Setting x = n/ϕ(n), by (2) and (7) we obtain the quadratic inequality

x^{2} − x − 1 > 0,

which has the positive solution x > α. Thus the right hand inequality is proved. Otherwise by (2)

\frac{σ(n)}{n} = 1 + \frac{1}{x} < 1 + \frac{1}{α} = α,

thus proving the left hand inequality.

Theorem 2. If n > 2 is a solution to (1) then n is an odd square.

Proof. If a and b are natural numbers, then σ(a)/a ≤ σ(b)/b whenever a | b. Thus if 4 | n,

\frac{σ(n)}{n} ≥ \frac{7}{4} > α,

whence n is not a solution to (1) by Theorem 1. Thus any even solution greater than 2 has the form n = 2r, where r > 1 is odd. Thus by (1), since ϕ(r) < r,

3σ(r) = 2r + ϕ(r) < 2r + r = 3r,

a contradiction. Hence n is odd. Since ϕ(n) is even, the right hand side of (1) is odd. Hence σ(n) is odd. For odd natural numbers n, σ(n) is odd if and only if n is square.

By Theorem 2, n = m^{2}, where m > 1 is odd, for all solutions n > 2 to (1). Since ϕ(m^{2}) = mϕ(m), it follows that by (1) that

σ(m^{2}) = m(m + ϕ(m)).  (8)

Thus we seek necessary conditions for an odd natural number m > 1 to satisfy (8). The cyclotomic polynomials Φ_{n}(x) may be defined recursively by Φ_{1}(x) = x − 1 and

x^{n} − 1 = ∏_{d|n} Φ_{d}(x)

for all n > 1. Thus

σ(p^{a}) = ∏_{\begin{matrix}d|a+1 \\ d>1 \end{matrix}} Φ_{d}(p)  (9)

for primes p and natural numbers a. Nagell [4, Thm. 94], has shown

Lemma 3. Let p and q be distinct odd primes and let h = e_{q}(p), where e_{q}(p) denotes the exponent to which p belongs modulo q. Then q | Φ_{n}(p) if and only if n = hp^{γ} for some γ ≥ 0. If γ > 0 then q∥Φ_{hp^{γ}}(p).

For prime p and natural number n we denote the p-valuation of n by v_{p}(n). Thus v_{p}(n) = k if and only if p^{k}∥n. By (9) and Lemma 3,

v_{q}(σ(p^{a})) = \begin{cases}0, & if h ∤ a + 1; \\ v_{q}(a + 1), & if h = 1; \\ v_{q}(p^{h} − 1) + v_{q}(a + 1), & if h > 1, h | a + 1. \end{cases}  (10)

3 Lower Bounds on ω(m)

The arithmetic function ω counts the number of prime power components of a natural number n; i.e., if n has the unique prime factorization n = p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{k}^{α_{k}}, then ω(n) = k.

Theorem 4. If m is a solution to (8) then ω(m) > 2.

Proof. That ω(m) > 1 follows from (6) and Theorem 1, since otherwise

\frac{m}{ϕ(m)} ≤ \frac{3}{2} < α,

contradicting Theorem 1.

Similarly if ω(m) = 2 then 3 | m, otherwise

\frac{m}{ϕ(m)} ≤ \frac{5}{4} · \frac{7}{6} < α.

Thus m = 3^{a}p^{b} for some odd prime p > 3 and natural numbers a and b. Then p ≥ 11 (by (5) and Theorem 1), otherwise

\frac{σ(m^{2})}{m^{2}} ≥ \frac{σ(3^{2})}{3^{2}} · \frac{σ(7^{2})}{7^{2}} = \frac{13}{9} · \frac{57}{49} > α.

Then p ≤ 13 (by (6) and Theorem 1), otherwise

\frac{m}{ϕ(m)} ≤ \frac{3}{2} · \frac{17}{16} < α.

Suppose p = 11. Thus m = 3^{a}11^{b}. Thus by (8),

σ(m^{2}) = σ(3^{2a}11^{2b}) = 3^{2a−1}11^{2b−1}(3 · 11 + ϕ(3 · 11)).

Since 33+ϕ(33) = 53, we have 53 | σ(3^{2a})σ(11^{2b}). By (10), this is impossible since e_{53}(3) = 52 and e_{53}(11) = 26.

Likewise p = 13 implies 63 | σ(3^{2a})σ(11^{2b}) for some natural numbers a and b; thus 3 | σ(11^{2b}), which is impossible since e_{3}(11) = 2.

Theorem 5. If m is a solution to (8) then ω(m) > 3.

Proof. By Theorem 4 it suffices to show that the assumption ω(m) = 3 is untenable. By (5), we have 3 | m, since otherwise

\frac{m}{ϕ(m)} ≤ \frac{5}{4} · \frac{7}{6} · \frac{11}{10} < α,

contradicting Theorem 1.

Thus m = 3^{a}p^{b}q^{c} for odd primes 3 < p < q and natural numbers a, b, and c. Similarly, 5 ∤ m and 7 ∤ m since otherwise

\frac{σ(m^{2})}{m^{2}} ≥ \frac{13}{9} · \frac{57}{49} > α.

Furthermore p ≤ 23 since otherwise

\frac{m}{ϕ(m)} ≤ \frac{3}{2} · \frac{29}{28} · \frac{31}{30} < α.

Thus p ∈ {11, 13, 17, 19, 23}. We shall prove that all the five cases are impossible. Note that by (8),

σ(3^{2a})σ(p^{2b})σ(q^{2c}) = 3^{2a−1}p^{2b−1}q^{2c−1}(3pq + 2(p − 1)(q − 1)).  (11)

Suppose p = 23. Then q ≤ 31 since otherwise

\frac{m}{ϕ(m)} ≤ \frac{3}{2} · \frac{23}{22} · \frac{37}{36} < α.

Note that 3 | σ(23^{2b})σ(q^{2c}) by (11), thus by (10) we have q ≡ 1 (mod 3), hence q = 31. Furthermore 3 | 2c + 1, hence Φ_{3}(31) | 3^{2a} · 23^{2b−1} · 31^{2c−1} · 1153 by (11). But this is impossible since 331 | Φ_{3}(31). Thus p ≠ 23.

Suppose p = 19. Then q ≤ 43 since otherwise

\frac{m}{ϕ(m)} ≤ \frac{3}{2} · \frac{19}{18} · \frac{47}{46} < α.

Thus q ∈ S, where S = {23, 29, 31, 37, 41, 43}. By (11) we have

σ(3^{2a})σ(19^{2b})σ(q^{2c}) = 3^{2a}19^{2b−1}q^{2c−1}(31q − 12).

We remark that 3 ∤ σ(19^{2b}), since otherwise by (9) and (10) we have 127 | 31q − 12 (as Φ_{3}(19) = 3 · 127), but this is false for all q ∈ S. Hence 3 | σ(q^{2c}), thus by (9) and (10), q ∈ {31, 37, 43} and Φ_{3}(q) | 3^{2a}19^{2b−1}(31q − 12); this is false. Thus p ≠ 19.

Suppose p = 17. Thus by (11)

σ(3^{2a})σ(17^{2b})σ(q^{2c}) = 3^{2a−1}17^{2b−1}q^{2c−1}(83q − 32).

By (9) and (10) we have 17 | σ(q^{2c}), thus q ≡ 1 (mod 17), hence q ≥ 103. Then

\frac{m}{ϕ(m)} ≤ \frac{3}{2} · \frac{17}{16} · \frac{103}{102} < α,

contradicting Theorem 1. Thus p ≠ 17.

Suppose p = 13. Then q ≥ 37 since otherwise

\frac{σ(m^{2})}{m^{2}} ≥ \frac{13}{9} · \frac{183}{169} · \frac{993}{961} > α.

Furthermore v_{3}(m) ≤ 2 since otherwise

\frac{σ(m^{2})}{m^{2}} ≥ \frac{1093}{729} · \frac{183}{169} > α.

Hence we consider the two cases, v_{3}(m) = 2 and v_{3}(m) = 1.

In the former case we have v_{13}(m) ≤ 2 since otherwise

\frac{σ(m^{2})}{m^{2}} ≥ \frac{121}{81} · \frac{5229043}{4826809} > α,

leaving two subcases, v_{13}(m) = 2 or v_{13}(m) = 1. The first subcase yields by (11),

11^{2} · 30941σ(q^{2c}) = 3^{4} · 13^{3}q^{2c−1}(21q − 8),

implying both that q = 30941 and 11 | 21q−8, a contradiction. Similarly, the second subcase yields

11^{2} · 61σ(q^{2c}) = 3^{3} · 13^{3}q^{2c−1}(21q − 8),

implying both that q = 61 and 11 | 21q − 8, a contradiction.

In the latter case, viz., v_{3}(m) = 1, we have by (11)

σ(13^{2b})σ(q^{2c}) = 3^{2} · 13^{2b−2}q^{2c−1}(21q − 8).  (12)

Note that

b > 1,  (13)

otherwise (12) yields 61σ(q^{2c}) = 3q^{2c−1}(21q − 8) whence q = 61. Thus σ(61^{2c}) = 3 · 61^{2c−2} · 19 · 67, thus c = 1, thus the contradiction 13 · 97 = 19 · 67. Since b > 1, it follows from (12) that 13 | σ(q^{2c}).

We show here q ≢ 1 (mod 13). Otherwise by (12) and (10) 2b − 2 = v_{13}(σ(q^{2c})) = v_{13}(2c+1), hence 2c+1 ≥ 13^{2b−2}, hence 2c−1 > 10^{b}. Thus (since (12) implies q^{2c−1} | σ(13^{2b})) we have σ(13^{2b}) ≥ q^{2c−1} > q^{10^{b}} > 13^{10^{b}} > 13^{2b+1} > σ(13^{2b}), a contradiction. Hence q ≢ 1 (mod 13); therefore by (10),

c ≡ 1 (mod 3);  (14)

furthermore

2b − 2 = v_{13}(σ(q^{2c}) = v_{13}(q^{2} + q + 1) + v_{13}(2c + 1).  (15)

Let t = v_{13}(2c + 1). Suppose t > 0. Since v_{13}(q + 2 + q + 1) < 3 log_{13} q, from (15) it follows that

2b − 2 < 3 log_{13} q + t.  (16)

Since 13^{t} | 2c + 1, we have 2c − 1 ≥ 13^{t} − 2, hence by (12)

13^{2b+1} > σ(13^{2b}) ≥ q^{2c−1} ≥ q^{13^{t}−2},

hence

2b − 2 > (13^{t} − 2) log_{13} q − 3.  (17)

By (16) and (17) it follows (since log_{13}(q) > 1) that

t > (13^{t} − 5) log_{13} q − 3 > 13^{t} − 8,

a contradiction if t ≥ 1. Therefore t = 0. Thus by (10), (12),

2b − 2 = v_{13}(σ(q^{2c})) = v_{13}(q^{2} + q + 1).  (18)

Since q^{2} + q + 1 < q^{3}, from (12) and (18) it follows that

13^{2b−1} > σ(13^{2b}) ≥ q^{2c−1} = (q^{3})^{\frac{2c−1}{3}} > (q^{2} + q + 1)^{\frac{2c−1}{3}} ≥ (13^{2b−2})^{\frac{2c−1}{3}}
= 13^{\frac{2}{3} (b−1)(c−2)}.

Thus 2b − 1 > \frac{2}{3}(b − 1)(2c − 1); equivalently, (b − 1)(c − 2) < \frac{9}{4}. Therefore (b − 1)(c − 2) ≤ 2. By (13) it follows that

c ≤ \frac{2b}{b − 1}.  (19)

By (14) we have c = 1 if b ≥ 3. Suppose b = 2. By (14), (19), c = 4 or c = 1. But c = 4 implies, by (12),

σ(13^{4})σ(q^{8}) = 3^{2} · 13^{2}q^{7}(21q − 8),

hence by (9) q^{7} | Φ_{5}(13) = 30941, a contradiction. Therefore c = 1 by (13). Hence by (12),

σ(13^{2b})(q^{2} + q + 1) = 3^{2} · 13^{2b−2}q(21q − 8).  (20)

By (13), (20), we have 13^{2} | q^{2} + q + 1, hence q ≥ 191.

We remark here that (20) is equivalent to

q = \frac{13^{2b+1} − 1}{13^{2b−2}(71q − 3061) + (q + 1)}.

Therefore

q < \frac{13^{2b+1}}{13^{2b−2}(71q − 3061)} = \frac{2197}{71q − 3061},

a contradiction since q ≥ 191. Therefore p ≠ 13.

Finally, suppose p = 11. By (3) and (5), we have 3∥m, otherwise

\frac{σ(m^{2})}{m^{2}} ≥ \frac{121}{81} · \frac{133}{121} > α,

contradicting Theorem 1. Thus by (11),

13σ(11^{2b})σ(q^{2c}) = 3 · 11^{2b−1}q^{2c−1}(53q − 20).  (21)

We show here q ≢ 1 (mod 11). Otherwise by (10), (21), 2b−1 = v_{11}(σ(q^{2c})) = v_{11}(2c+1), hence 2c + 1 ≥ 11^{2b−1}. Thus by (21),

11^{2b+1} > σ(11^{2b}) ≥ q^{2c−1} ≥ q^{11^{2b−1}−2},

thus 2b + 1 > (11^{2b−1} − 2) log_{11} q > 11^{2b−1} − 2, a contradiction.

Therefore q ≢ 1 (mod 11). By (10), e_{11}(q) = 5 (whence q > 13) and thus

5 | 2c + 1;  (22)

furthermore by (21)

2b − 1 = v_{11}(σ(q^{2c})) = v_{11} (Φ_{5}(q)) + v_{11}(2c + 1).  (23)

Let t = v_{11}(2c + 1). Suppose t > 0. Since Φ_{5}(q) < q^{5}, we have by (23)

2b − 1 < 5 log_{11} q + t.  (24)

On the other hand, since 2c + 1 ≥ 11^{t}, (21) yields 11^{2b+1} > σ(11^{2b}) ≥ q^{2c−1} ≥ q^{11^{t}−2}, hence

2b + 1 > (11^{t} − 2) log_{11} q.  (25)

Then (24), (25), together imply

t > (11^{t} − 7) log_{11} q − 2 > 11^{t} − 9,

which is impossible for t ≥ 1. Therefore t = 0. Hence by (23)

2b − 1 = v_{11} (Φ_{5}(q)) .  (26)

Since Φ_{5}(q) < q^{5}, we have by (21), (26),

11^{2b+1} > σ(11^{2b}) ≥ q^{2c−1} = (q^{5})^{\frac{2c−1}{5}} > (Φ_{5}(q))^{\frac{2c−1}{5}} ≥ (11^{2b−1})^{\frac{2c−1}{5}} .

Thus 2b + 1 > \frac{1}{5}(2b − 1)(2c + 1); equivalently,

c < \frac{6b + 2}{2b − 1}.  (27)

By (10), 3 ∤ σ(11^{2b}) since e_{3}(11) = 2. Thus by (21), we have 3 | σ(q^{2c}), hence by (10) 3 | 2c + 1. Thus by (22), 15 | 2c + 1, hence c ≥ 7. Thus by (27) we have b = 1, c = 7. Thus by (21)

7 · 13 · 19σ(q^{14}) = 3 · 11q^{13}(53q − 20),

implying q^{13} | 1729, which is impossible. Therefore p ≠ 11, thus completing the proof.

4 Results on the shape of m

By the shape of a natural number, we mean the nature of the exponents of the prime factors in the unique prime factorization of that number. We have already seen in Theorem 2 that a solution n > 2 to (1) must be an odd square, n = m^{2}, as in (8). We seek necessary conditions on the shape of m.

Theorem 6. If m is a solution to (8) then m is neither squarefree nor the square of a squarefree natural number.

Proof. First suppose that m is squarefree. By (9), σ(m^{2}) is the product of cyclotomic polynomials Φ_{3}(p) evaluated at the prime divisors p of m. Thus by Lemma 3, if q is a prime dividing σ(m^{2}), then either q = 3 or q ≡ 1 (mod 3). Thus by (8), since m | σ(m^{2}),

m = 3^{ϵ}p_{1}p_{2} ⋯ p_{k},

where ϵ ∈ {0, 1} and p_{1} < p_{2} < ⋯ < p_{k} are primes such that p_{j} ≡ 1 (mod 3), 1 ≤ j ≤ k. By Lemma 3 we have 3∥Φ_{3}(p_{j}), 1 ≤ j ≤ k, hence v_{3}(σ(m^{2})) = k. Since k ≥ 3 by Theorem 5, we have 3^{2} | ϕ(m), hence 3^{ϵ}∥m + ϕ(m), hence

v_{3}(m(m + ϕ(m)) = 2ϵ.

Thus by (8), k = 2ϵ, a contradiction since k ≥ 3 and ϵ ≤ 1. Hence m cannot be squarefree.

Now suppose that m is the square of a squarefree natural number. As above, σ(m^{2}) is the product of cyclotomic polynomials Φ_{5}(p) evaluated at the prime divisors p of m, hence if q is a prime dividing σ(m^{2}), then either q = 5 or q ≡ 1 (mod 5); consequently

m = 5^{ϵ}p_{1}^{2}p_{2}^{2} ⋯ p_{k}^{2},

where ϵ ∈ {0, 2} and p_{1} < p_{2} < ⋯ < p_{k} are primes such that p_{j} ≡ 1 (mod 5), 1 ≤ j ≤ k. Again, as above, v_{5}(σ(m^{2})) = k. Since k ≥ 3 by Theorem 5, we have 5^{3} | ϕ(m), hence 5^{ϵ}∥m + ϕ(m), hence

v_{5}(m(m + ϕ(m)) = 2ϵ.

Thus k = 2ϵ, hence k = 4. Thus by (6)

\frac{m}{ϕ(m)} ≤ \frac{5}{4} · \frac{11}{10} · \frac{31}{30} · \frac{41}{40} · \frac{61}{60} < α,

contradicting Theorem 1. Hence m is not the square of a squarefree natural number.

5 Concluding Remarks

A natural number n is said to be perfect if σ(n) = 2n. No odd perfect numbers are known, and the question regarding their existence remains what is widely believed to be the oldest unsolved problem in all of mathematics. It seems the question of whether (1) has any solutions n > 2 parallels that regarding the existence of odd perfect numbers. For example, the only even solution to (1) is 2, while the even solutions to σ(n) = 2n are in one-to-one correspondence with the set of Mersenne primes, and are thus characterized completely. On the other hand, no odd solutions to (1), or to σ(n) = 2n, are known. In either case, the only results known are those stating necessary conditions for such solutions to exist. Considering the difficulty involved in proving Theorem 5, it is clear that the problem regarding solutions n > 2 to (1) is no less difficult than that of the existence of odd perfect numbers.

All calculations for this paper were done by hand. This was in fact quite easy, since the bulk of the work comprised comparing rational numbers to the golden ratio, α. This entailed computing the first few convergents of the rational number in question until a partial quotient exceeded 1, a task easily done by hand. Otherwise, some of the factorizations of cyclotomic polynomials given were found in Brillhart et al. [1].

References

[1] J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. Wagstaff, Factorizations of b^{n} ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers, Amer. Math. Soc., 3rd edition, 2002.

[2] R. Guy, Unsolved Problems in Number Theory,, 3rd edition, Springer-Verlag, 2004.

[3] G. Hardy and E. Wright, An Introduction to the Theory of Numbers, Oxford at the Clarendon Press, 4th edition, 1960.

[4] T. Nagell, Introduction to Number Theory, Wiley, 1951.

[5] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, https://oeis.org.

2010 Mathematics Subject Classification: Primary 11A25.

Keywords: sum of divisors, Euler totient. (Concerned with sequences \underline{A055940}, \underline{A066679}, and \underline{A070159}.) Received January 9 2017; revised version received May 22 2017. Published in Journal of Integer Sequences, June 25 2017. Return to Journal of Integer Sequences home page.