On the Ratio of the Sum of Divisors and Euler’s Totient Function II

Kevin A. Broughan and Qizhi Zhou Department of Mathematics University of Waikato Private Bag 3105 Hamilton New Zealand

                       kab@waikato.ac.nz
                      qz49@waikato.ac.nz

Abstract We find the form of all solutions to ϕ(n) | σ(n) with three or fewer prime factors,

except when the quotient is 4 and n is even.

1 Introduction

In this article we continue the study of the sets

R_{a} = {n ∈ ℕ : σ(n) = a · ϕ(n)}

for integer a ≥ 2, begun in [3]. Motivation for this is given in the introduction of [3]. That article was concerned primarily with R_{2}. It was shown that the only solutions to the equation σ(n) = 2 · ϕ(n), with at most 3 distinct prime factors are 3, 35 and 1045, that there exist at most a finite number of solutions to σ(n) = 2 · ϕ(n) with Ω(n) ≤ k, and that there are at most 2^{2^{k}+k} − k squarefree solutions to ϕ(n) | σ(n) if ω(n) = k. It was also shown that the number of solutions to ϕ(n) | σ(n) has asymptotic density zero.

Here is an outline of this article. Other than in an exceptional case, we derive a complete list of all forms of divisibilities ϕ(n) | σ(n) for all n having less than 4 distinct prime factors.

There are only finitely many distinct such n if and only if the set of Mersenne primes together with all primes of the form 2 · 3^{n} − 1 is finite. The finiteness or otherwise of these sets of primes are commonly regarded as ultra-difficult questions to resolve, and we do not treat this issue here.

The explicit values of n for which ϕ(n) | σ(n) are given in Theorem 25 and summarized in Tables 1 and 2. The exceptional case is where the quotient is 4 and n is even. Here there appears to be an infinite number of solutions, but we have not been able to show this, even assuming well known conjectures relating to properties of primes.

In Section 2 we develop some tools which are needed later. In Lemma 6 and Theorem 9 we give a complete list of the finite number of n in any R_{a} with fewer than 3 prime factors. Then we give in Lemma 12 a complete list of the elements of R_{3} with 3 distinct prime factors. Here this list if finite if and only if the set of primes of the form 2 · 3^{n} − 1 is finite. In Lemma 14 we do the same for the odd elements of R_{4}. Of special interest is the relationship of R_{4}, and some of the other R_{a}, to Mersenne primes. The even elements of R_{4} with two prime factors are precisely numbers of the form 2^{p−2}M_{p} (Lemma 13). Conjecturally [6] the set of elements of R_{4} with two prime factors is infinite. In Section 6 we study the case for larger values of a. In Lemmas 16 and 18 we determine all of the R_{a} with a ≥ 10. The methods used in these cases rely on the algorithmic content of the method used for the case a = 2 [3, Lemma 10], the finiteness of the set of solutions when the primes are fixed, [3, Theorem 17], simple inequalities and properties of multiplicative orders.

The case a = 9 proved hardest to resolve, requiring properties of primitive prime divisors of Lucas sequences, Lemma 21.

Finally, in Section 7 we describe a heuristic procedure which generates squarefree elements of R_{2} with a specified number of prime factors. We give examples for 1 ≤ ω(n) ≤ 10. This is evidence that R_{2} is infinite, but we have made no progress in showing this.

a ω(n) n  factors
2 1  3  3
3 1  2  2
3 2  15  3 · 5
3 3  *  3^{α} · 7 · N_{α+1}
3 3  5049  3^{3} · 11 · 17
4 2  Mersenne 2^{p−2}M_{p}
4 3  105  3 · 5 · 7
4 3  1485  3^{3} · 5 · 11
5 3  190  2 · 5 · 19
5 3  812  2^{2} · 7 · 29
5 3  1672  2^{3} · 11 · 19
5 3  56252  2^{2} · 7^{3} · 41

Table 1: Solutions to σ(n) = a · ϕ(n) for 2 ≤ a ≤ 5.

a ω(n) n  factors
6 3  616  2^{3} · 7 · 11
6 3  79000  2^{3} · 5^{3} · 79
6 3  Mersenne 2^{p−2} · 5 · M_{p}
7 3  78  2 · 3 · 13
7 3  140  2^{2} · 5 · 7
7 3  2214  2 · 3^{3} · 41
7 3  25758  2 · 3^{5} · 53
8 3  594  2 · 3^{3} · 11
8 3  7668  2^{2} · 3^{3} · 71
8 3  Mersenne 2^{p−2} · 3 · M_{p}
9 3  30  2 · 3 · 5
9 3  264  2^{3} · 3 · 11
9 3  61344  2^{5} · 3^{3} · 71
10 3  168  2^{3} · 3 · 7
10 3  270  2 · 3^{3} · 5
10 3  2376  2^{3} · 3^{3} · 11
13 3  27000  2^{3} · 3^{3} · 5^{3}

Table 2: Solutions to σ(n) = a · ϕ(n) for 6 ≤ a ≤ 13.

We believe the number of solutions to σ(n) = 4 · ϕ(n) having the form n = 2^{e} · p · q, with p, q being odd primes, is infinite, but new methods will be needed to show this. For example with e = 23 we find 33 solutions. So at least with ω(n) ≤ 3, 4 is the only integer quotient σ(n)/ϕ(n) yet to be fully resolved. We expect new methods will be needed to do this.

Notation: ϕ(n) is Euler’s totient function, σ(n) the sum of divisors of n, ω(n) the number of distinct prime divisors of n, Ω(n) the total number of prime divisors counted with multiplicity, ν_{p}(n) is the maximum power of the prime p which divides n, and a ∥ n means a divides n with gcd(a, n/a) = 1. The Landau-Vinogradov symbols o, O, ≪, ≍ each have their usual meaning, with all implied constants being absolute. The expression e = ord_{p} a means e is the minimum positive integer such that a^{e} ≡ 1 (mod p). If so, e is called the multiplicative order of a, modulo p. If a > b are natural numbers satisfying gcd(a, b) = 1, then R = R_{a/b} denotes the set of solutions to σ(n)/ϕ(n) = a/b with the convention that R_{a} = R_{a/1}. Finally M_{p} represents the Mersenne prime 2^{p} − 1 and N_{a} any prime of the form 2 · 3^{a} − 1.

Note that in what follows we often use the function h(n) := σ(n)/ϕ(n), h : ℕ → ℚ. If u properly divides v then h(u) < h(v) [3, Lemma 4]. If n ∈ R_{a} has the prime decomposition n = p_{1}^{α_{1}} ⋯ p_{k}^{α_{k}} it satisfies

h(p_{1}^{α_{1}}) ⋯ h(p_{k}^{α_{k}}) = a.  (1)

2 Properties of R_{a}

We begin with some preliminary inequalities.

Lemma 1. Let n ∈ R_{a} satisfy for all p | n, p ≥ p_{0}. If n = ∏_{i=1}^{k} p_{i}^{α_{i}} let

p_{j}^{α_{j}+1} = min{p_{i}^{α_{i}+1} : 1 ≤ i ≤ k}.

Then

m := (aζ(2) ∏_{p<p_{0}} (1 − \frac{1}{p^{2}} ))^{− \frac{1}{2}} < ∏_{p | n} (1 − \frac{1}{p}) < (\frac{a}{1 − _{\frac{1}{p_{j}^{α_{j} +1}}}} )^{− \frac{1}{2}} =: M.

Proof. Since

∏_{i=1}^{k} (1 − \frac{1}{p_{i}^{α_{i}+1}} ) = a · ∏_{i=1}^{k} (1 − \frac{1}{p_{i}} )^{2}  (2)

the upper bound is immediate. For the lower bound we can write

a · ∏_{i=1}^{k} (1 − \frac{1}{p_{i}} )^{2} = ∏_{i−1}^{k} (1 − \frac{1}{p_{i}^{α_{i}+1}} ) > ∏_{p≥p_{0}} (1 − \frac{1}{p^{2}} ) = (ζ(2) ∏_{p<p_{0}} (1 − \frac{1}{p^{2}} ))^{−1} ,

and the Lemma follows.

Note that if n ∈ R_{a} and P (n), p(n) are respectively the maximum and minimum primes dividing n, and m, M are defined as in Lemma 1, then

p(n) < \frac{1}{1 − M^{\frac{1}{ω(n)}}} and \frac{1}{1 − m^{\frac{1}{ω(n)}}} < P (n).

From Lemma 1 we get for n ∈ R_{a} an inequality which is used frequently in what follows:

∏_{p | n} (1 − \frac{1}{p}) < \frac{1}{\sqrt{a}}.  (3)

Corollary 2. If p(n) is the minimum prime dividing n ∈ R_{a} then 3ω(n) > p(n) log a.

Proof. Let p_{0} = p(n) and use − log(1 − x) < 3x/2, which is valid for real x with 0 < x < 1/2, to get 1/\sqrt{a} > ∏_{p | n}(1 − 1/p) ≥ (1 − 1/p_{0})^{ω(n)}, taking logarithms to complete the derivation.

The following lemmas show that as a increases the number of distinct prime factors in any member of R_{a} also increases.

Lemma 3. Let n ∈ R_{a} with 2 ≤ a ≤ 24. If n is even we have the lower bounds ω(n) ≥ B with (a, B) in

{(2, 1), (3, 1), (4, 2), (5, 2), (6, 2), (7, 2), (8, 2), (9, 3), (10, 3), (11, 3), (12, 3), (13, 3),

(14, 3), (15, 4), (16, 4), (17, 4), (18, 4), (19, 4), (20, 5), (21, 5), (22, 5), (23, 5), (24, 6)}.

If n is odd then we have the lower bounds ω(n) ≥ B with (a, B) in

{(2, 1), (3, 2), (4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (9, 8), (10, 9), (11, 11), (12, 13), (13, 15), (14, 17), (15, 19), (16, 21), (17, 24), (18, 27), (19, 30), (20, 33), (21, 37), (22, 41), (23, 45),

(24, 49), (25, 54), (26, 60), (27, 65), (28, 72)}.

Proof. If P_{n} is the n’th prime with P_{1} = 2, because p_{i} ≥ P_{i} for 1 ≤ i ≤ n we have

\frac{1}{\sqrt{a}} > ∏_{i=1}^{m} (1 − \frac{1}{p_{i}} ) ≥ ∏_{i=1}^{m} (1 − \frac{1}{P_{i}} ) .

So if for some m ∈ ℕ we have

∏_{i=1}^{m} (1 − \frac{1}{P_{i}} ) ≥ \frac{1}{\sqrt{a}}

since the product is strictly decreasing in m, we must have m < ω(n). So for given a ≥ 2, we evaluate this product until its value is less than 1/\sqrt{a}. The value of m is then a lower bound for ω(n).

Lemma 4. Let n ∈ R_{a}. If n is even and ω(n) ≥ 6, and we set c_{1} := 0.317 then

ω(n) > exp (c_{1}\sqrt{a}) .  (4)

If n is odd and ω(n) ≥ 5 then

ω(n) > exp (2c_{1}\sqrt{a}) − 1.  (5)

Proof. We use the same approach taken in the proof of Lemma 3. First we claim that for x ≥ 6 we have

log(x(log x + loglog x)) ≤ \frac{3}{2} log x.

This inequality is equivalent to f(x) := e^{\sqrt{x}}/x − log x ≥ 0 which is true at x = 6, 7, 8. The derivative

f′(x) = \frac{\sqrt{x}e^{\sqrt{x}} − 2e^{\sqrt{x}} − 2x}{2x^{2}}

has a positive numerator for x ≥ 9, demonstrating the claim.

This, together with the formulas (3.13) and (3.27) of [5] enable us to write for m ≥ 6:

\frac{1}{\sqrt{a}} > ∏_{i=1}^{m} (1 − \frac{1}{P_{i}} )

≥ \frac{e^{−γ}}{log P_{m}} (1 − \frac{1}{log^{2} P_{m}} )
> \frac{e^{−γ} · 0.848}{log (m(log m + log log m))}
> \frac{e^{−γ} · 0.848}{1.5 log m} > \frac{c_{1}}{log m}.

Hence, replacing m by ω(n) and using Lemma 3 we get ω(n) ≥ exp(c_{1}\sqrt{a}). A small modification gives the bound when n is odd.

Note that the larger lower bound when n is odd stems from the factor 1/2 being missing from the related product. Now using Lemma 3 and Lemma 4, because for a ≥ 28 we have exp(2c_{1}\sqrt{a}) > a, we get

Corollary 5. If n ∈ R_{a} is odd then ω(n) ≥ a − 1.

Lemma 6. If n ∈ R_{a}, ω(n) = 1 and a ≥ 2 then a = 2 and n = 3 or a = 3 and n = 2.

Proof. If n = p^{α} we get p^{α+1} − 1 = ap^{α−1}(p − 1)^{2} so p^{α−1} | p^{α+1} − 1 giving α = 1. Then (p^{2} − 1) = a(p − 1)^{2} so p = (a + 1)/(a − 1) so a − 1 | a + 1 giving a = 2 or a = 3.

Note that if n ∈ R_{a} has n > 3 there exists a prime p | n with p < 1/(1 − a^{−1/(2ω(n)}), i.e., n is always divisible by a relatively small prime. To see this we can assume ω(n) ≥ 2. If n = ∏_{i=1}^{m} p_{i}^{α_{i}} then, by Equation (1), ∏_{i=1}^{m} h(p^{α_{i}}) = a so there exists a i with h(p_{i}^{α_{i}}) > a^{1/ω(n)}. Then

\frac{1}{(1 − \frac{1}{p})^{2}} > h(p_{i}^{α_{i}}) > a^{\frac{1}{ω(n)}}

and the upper bound follows.

Here we extend [3, Theorem 17] to see that the quotient 2 can be replaced by any positive rational a > 1. That is to say, given such an a and a finite set of primes P, there exists at most a finite number of positive integers n with supp(n) ⊂ P and such that σ(n)/ϕ(n) = a. To see this note that the same proof [3] works for any such fixed rational number a, not just for a = 2.

Lemma 7. Let P be a finite set of primes and a > 1 a rational number. Then there exist at most a finite number of positive integers N ∈ ℕ with supp(N) ⊂ P such that σ(N)/ϕ(N) = a.

Now we show that when the primes are fixed the finite set of exponents for any n ∈ R_{a}, guaranteed by Lemma 7, can be found using an algorithm. The Mathematica code for this algorithm, as applied in the paper, is available from the first author. It is in essence a generalization of the method used to prove [3, Lemma 10].

Theorem 8. Let n = ∏_{i=1}^{k} p_{i}^{β_{i}} satisfy σ(n) = a · ϕ(n), where a is a positive rational number with a > 1, and suppose that the p_{i} are fixed. Then there is an algorithm (denoted here Algorithm A) which returns all possible values of the sets of of exponents β_{i}.

Proof. Set a_{k} := a. Then

∏_{i=1}^{k} (1 − \frac{1}{p_{i}^{β_{i}+1}} ) = a_{k} ∏_{i=1}^{k} (1 − \frac{1}{p_{i}} )^{2} < 1.

Taking logarithms we get

\frac{k}{p_{1}^{min(β_{i})+1} − 1} ≥ ∑_{i=1}^{k} \frac{1}{p_{i}^{β_{i}+1}} > − log (a_{i} ∏_{i=1}^{k} (1 − \frac{1}{p_{i}} )^{2}) =: λ_{k} > 0

so min(β_{i}) ≤ ⌊log (\frac{k}{λ_{k}} + 1) − 1⌋ =: min_{k}.

We then allow this minimum to be attained successively by β_{j} for 1 ≤ j ≤ k and to take each of the values 1 ≤ β_{j} ≤ min_{k}. Inserting each of these explicit values gives the equation

∏_{i=1,i≠j}^{k} (1 − \frac{1}{p_{i}^{β_{i}+1}} ) = a_{k−1} ∏_{i=1,i≠j}^{k} (1 − \frac{1}{p_{i}} )^{2} < 1.

where a_{k−1} = a_{k}(1 − 1/p_{j})^{2}/(1 − 1/p_{j}^{β_{j}+1}), which reduces the problem by one factor.

Proceeding in this manner, once k = 1 is reached the solutions are assembled, duplicates are removed and the full solutions checked against the original equation σ(n) = a · ϕ(n).

We expect the complexity of this algorithm to be

O(a · k! · (log 2k)^{k} · max(p_{i} : 1 ≤ i ≤ k)),

but since we used it only for k = 3, we did not consider optimizing improvements.

In the next theorem we describe all of the R_{a} with ω(n) = 2 except for a = 4. That case is completely characterized in Lemma 13 below. Also a = 2 is [3, Lemma 9] and a = 3 Lemma 11 below.

Theorem 9. Let n ∈ R_{a}.

• If ω(n) = 1 then a = 2 ⟹ n = 3, a = 3 ⟹ n = 2 and there are no solutions for a > 3.

• If ω(n) = 2 then a = 2 ⟹ n = 35, a = 3 ⟹ n = 15, a = 5 ⟹ n = 56, a = 6 ⟹ n = 6 and a = 7 ⟹ n = 12.

• For a > 7 there are no solutions to σ(n) = a · ϕ(n) with ω(n) = 2.

Proof. The first part is a restatement of Lemma 6.

Let ω(n) = 2. By Equation (3), if n = p^{u}q^{v} where p < q are primes we have

1/\sqrt{a} > (1 − 1/p)(1 − 1/q) ≥ (1 − 1/2)(1 − 1/3)

which implies 2 ≤ a ≤ 8. From the remark given above we can assume 5 ≤ a ≤ 8. By Corollary 5 we have for n odd 3 ≥ a so n must be even. Then 1/\sqrt{a} > (1 − 1/2)(1 − 1/q). That gives q < 1/(1 − 2/\sqrt{a}) so a = 5 ⟹ q ∈ \{3, 5, 7\}, a = 6 ⟹ q ∈ \{3, 5\}, a = 7, 8 ⟹ q = 3. We then apply Algorithm A with the explicit values for a, p = 2 and given values of q to find the solutions given in the statement of the lemma.

3 Properties of R_{3}

Lemma 10. If n ∈ R_{3} and n > 2 then n is odd.

Proof. If n = 2^{e} · m with m odd, m > 1 and e ≥ 1, then

1 < \frac{σ(n)}{ϕ(n)} = \frac{2^{e+1} − 1}{2^{e−1}} \frac{σ(m)}{ϕ(m)} = 3,

so

1 < \frac{σ(m)}{ϕ(m)} = \frac{3 · 2^{e−1}}{2^{e+1} − 1} ≤ 1.

Therefore, since by Lemma 6, m = 1 is not possible, we must have e = 0, so n is odd.

Lemma 11. If n ∈ R_{3} and ω(n) = 2 then n = 15.

Proof.

(1) Let n = p^{α}·q^{β}. First note that the term 1/(1−1/p) is decreasing as p increases. Therefore if both p, q ≥ 5 one finds

2.13 ≥ \frac{1}{(1 − \frac{1}{p})^{2}(1 − \frac{1}{q})^{2}} ≥ \frac{(1 − \frac{1}{p^{α+1}} )(1 − \frac{1}{q^{β+1}} )}{(1 − \frac{1}{p})^{2}(1 − \frac{1}{q})^{2}} = 3.

Thus we can assume 3 = p < q.

(2) Suppose that p = 3 and q ≥ 11, in which case

\frac{(3^{α+1} − 1)/2}{3^{α−1} · 2} · \frac{1 − \frac{1}{q^{β+1}}}{(1 − \frac{1}{q})^{2}} = 3.

Now the second term on the right is decreasing in q, so is strictly bounded above by 1/(1 − 1/11)^{2} = 121/100. It follows that \frac{3^{α+1}−1}{4·3^{α−1}} · \frac{121}{100} > 3, whence

3^{α+1} > 3^{α+1} − 1 > \frac{300 · 4}{121 · 9} · 3^{α+1} = \frac{400}{363} · 3^{α+1} > 3^{α+1}

and the last statement is clearly false. Hence we can assume p = 3 and q ∈ {5, 7}.

(3) If p = 3 and q = 5, since n = 15 is a solution to σ(n) = 3 · ϕ(n), so by [3, Lemma 4], no proper multiple is also a solution, leaving 15 as the only solution in this case.

(4) For p = 3 and q = 7 Algorithm A shows there are no solutions of the form n = p^{α}q^{β}.

Lemma 12. If n ∈ R_{3} and ω(n) = 3 then n ∈ {3^{α} · 7 · N_{α+1}, 5049} where N_{α+1} is any prime of the form 2 · 3^{α+1} − 1.

Proof.

(1) We can assume n > 15 and, by Lemma 10, n is odd. Each of 357 = 3·7·17, 3339 = 3^{2}·7·53, and 5049 = 3^{3} · 11 · 17 is a solution to σ(n) = 3ϕ(n), so we will assume that these three solutions have already been found. Because

(1 − \frac{1}{5}) (1 − \frac{1}{7}) (1 − \frac{1}{11}) > \frac{1}{\sqrt{3}}

we must have 3 | n. So assume n = 3^{α}p^{β}q^{γ} with 3 < p < q.

(2) We will now show 5 ∤ n. To see this, first assume n = 3^{α} · 5^{β} · q^{c} with 5 < q. Then

(1 − \frac{1}{3^{2}} ) (1 − \frac{1}{5^{2}} ) (1 − \frac{1}{q^{2}} ) ≤ (1 − \frac{1}{3^{α+1}} ) (1 − \frac{1}{5^{β+1}} ) (1 − \frac{1}{q^{γ+1}} )

= 3 (1 − \frac{1}{3})^{2} (1 − \frac{1}{5})^{2} (1 − \frac{1}{q})^{2} .

Therefore

(\frac{64}{75}) (1 − \frac{1}{q^{2}} ) ≤ (\frac{64}{75}) (1 − \frac{1}{q})^{2}

or (1 + 1/q) ≤ (1 − 1/q) which is false. Therefore 5 ∤ q.

(3) Now at least one of p, q must be less than 13: if not we would have

0.867 > \frac{3}{2\sqrt{3}} > (1 − \frac{1}{p}) (1 − \frac{1}{q}) ≥ (1 − \frac{1}{13}) (1 − \frac{1}{17}) > 0.868.

Hence, by (1) and (2) we must have p ∈ {7, 11}. We consider each of these possibilities.

(4) First let p = 11 so n = 3^{α}11^{β}q^{γ}. By Equation (2) we have

1 > (1 − \frac{1}{3^{α+1}} ) (1 − \frac{1}{11^{β+1}} ) (1 − \frac{1}{q^{γ+1}} ) = \frac{1200}{1089} (1 − \frac{1}{q})^{2} .

This implies 13 ≤ q < 1/(1 − \sqrt{1089/1200}) < 22 so q ∈ \{13, 17, 19\}. Algorithm A gives no new solution.

(5) Now let p = 7 so n = 3^{α}7^{β}q^{γ} and let β ≥ 2. We have

(1 − \frac{1}{3^{α+1}} ) ≤ \frac{56}{57} \frac{1}{h(q^{γ})} < \frac{56}{57}.

Therefore 3^{α+1} < 57 so α ∈ {1, 2} when β ≥ 2. (5.1) Consider the case α = 1 so n = 3 · 7^{β} · q^{γ} still with β ≥ 2. Then Equation (2) gives

1 > (1 − \frac{1}{7^{β+1}} ) (1 − \frac{1}{q^{γ+1}} ) = \frac{54}{49} (1 − \frac{1}{q})^{2}

so 11 ≤ q ≤ 1/(1 − \sqrt{49/54}) < 22 and Algorithm A gives only the solution n = 3 · 7 · 17. (5.2) Now consider the case α = 2 so n = 3^{2} · 7^{β} · q^{γ} with β ≥ 2. Then

(1 − \frac{1}{7^{β+1}} ) (1 − \frac{1}{q^{γ+1}} ) = \frac{648}{637} (1 − \frac{1}{q})^{2} < 1

so q < 1/(1 − \sqrt{637/648}) < 117.4 so

q ∈ {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,

71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113}.

Algorithm A gives no new solution. (5.3) By (5), (5.1) and (5.2), if p = 7 then we can assume β = 1.

(6) Let p = 7. We can write n = 3^{α}7^{1}q^{γ} with q ≥ 11. By [3, Lemma 4], we have

\frac{1}{h(q^{γ})} ≤ \frac{1}{h(q)} = \frac{q − 1}{q + 1} = 1 − \frac{2}{q + 1}

so therefore, using Equation (2),

(1 − \frac{1}{3^{α+1}} ) ≤ \frac{3(2/3)^{2}(6/7)^{2}}{1 − 7^{−2}} · (1 − \frac{2}{q + 1})

giving 3^{α+1} ≤ (q + 1)/2.

(7) If n = 3^{α} · 7 · q^{γ} then using Equation (2) we get

(1 − \frac{1}{3^{α+1}} ) (1 − \frac{1}{q^{γ+1}} ) = (1 − \frac{1}{q})^{2} .

This equation can be rewritten

q^{γ−1} (−q^{2} + 2 · 3^{α+1}q − 3^{α+1}) = 3^{α+1} − 1,

which shows that q^{γ−1} | 3^{α+1} − 1. Thus if γ > 1 we must have q ≤ 3^{α+1} − 1, which is a contradiction, since by part (6), 3^{α+1} < (q+1)/2. Hence p = 7 implies γ = 1 and we can write n = 3^{α} · 7 · q. Putting this form into Equation (2) and solving gives q = 2 · 3^{α+1} − 1 =: N_{α+1}, so the right side is prime. Conversely every n of the form

n = 3^{α} · 7 · N_{α+1}

with N_{α+1} prime is in R_{3}.

4 Properties of R_{4}

Every n = 2^{p−2}M_{p}, where M_{p} := 2^{p} − 1 is prime, is in R_{4}. Conversely

Lemma 13. If n ∈ R_{4} is even with ω(n) = 2 then n = 2^{p−2}M_{p} with M_{p} prime.

Proof. Let n = 2^{e}p^{α} with α > 1 and e ≥ 1. Then 2^{e+1}p^{α−1}(p − 1)^{2} = (2^{e+1} − 1)(p^{α+1} − 1), or in other words,

\frac{2^{e+1}}{2^{e+1} − 1} = \frac{p^{α} + p^{α−1} + ⋯ + 1}{p^{α} − p^{α−1}}
1 + \frac{1}{2^{e+1} − 1} = 1 + \frac{2p^{α−1} + p^{α−2} + ⋯ + 1}{p^{α} − p^{α−1}}
2^{e+1} − 1 = \frac{p^{α} − p^{α−1}}{2p^{α−1} + ⋯ + 1}.

Therefore (2p^{α−1} + ⋯ + 1) | p − 1 which is false. Hence α = 1 and n = 2^{e}p.

Substituting this form into σ(n) = 4ϕ(n) we get (2^{e+1} − 1)(p + 1) = 2^{e+1}(p − 1). Solving this we get p = 2^{e+2} − 1. Thus q := e + 2 is prime and n = 2^{q−2}M_{q}, where M_{q} is a Mersenne prime.

Lemma 14. If n ∈ R_{4} is odd and ω(n) = 3 then n ∈ {105, 1485}.

Proof. Let n = p^{α}q^{β}r^{γ} with 3 < p < q < r. By Equation (3), if p ≥ 5 then

\frac{1}{2} = \frac{1}{\sqrt{4}} > (1 − \frac{1}{5}) (1 − \frac{1}{7}) (1 − \frac{1}{11}) = \frac{48}{77} > \frac{1}{2},

so p = 3 and we can write n = 3^{α}q^{β}r^{γ}. If r > q ≥ 7 then we would get

\frac{3}{4} > (1 − \frac{1}{7}) (1 − \frac{1}{11}) = \frac{60}{77} > \frac{3}{4}

which forces q = 5. Then a final application of Equation (3) gives

\frac{1}{2} > \frac{2}{3} · \frac{4}{5} (1 − \frac{1}{r}) ⟹ r < 16,

so we have r ∈ {7, 11, 13}. We take each of these possibilities separately.

(1) If r = 7 then Equation (1) gives

(1 − \frac{1}{3^{α+1}} ) h(5^{β})h(7^{γ}) = \frac{16}{9} ⟹ 1 − \frac{1}{3^{α+1}} = \frac{16}{9h(5^{β})h(7^{γ})} ≤ \frac{16}{9h(5)h(7)} = \frac{8}{9},

which implies α = 1 so n = 3^{1}5^{β}7^{γ} and h(3)h(5^{β})h(7^{γ}) = 4 which gives h(5^{β}7^{γ}) = 2. But in R_{2} we see the solution 5 · 7 so β = γ = 1 is the only possibility in this case. Hence n = 3 · 5 · 7 = 105.

(2) If r = 11 the same approach adopted in (1) gives α ∈ {1, 2, 3}. We treat each of these possibilities separately.

If α = 1 then we must have h(5^{β}11^{γ}) = 2 but, by Theorem 9 there is no solution in R_{2} of the form 5^{β}11^{γ}.

If α = 2 then Equation (2) gives

(1 − \frac{1}{5^{β+1}} ) (1 − \frac{1}{11^{γ+1}} ) = \frac{1536}{13 · 11^{2}}

but 13 does not divide the denominator of the left hand side.

If α = 3, since n = 3^{3} · 5 · 11 = 1485 is a solution there are none others with β > 1 or γ > 1.

(3) If r = 13 we have n = 3^{α}5^{β}13^{γ} so if β ≥ 2 and γ ≥ 1 we can write

1 − \frac{1}{3^{α+1}} ≤ \frac{16}{9h(5^{2})h(13)} = \frac{640}{651} ⟹ α ∈ \{1, 2\}.

If in this situation α = 1 then Equation (1) gives h(5^{β}13^{γ}) = 2, which has no solution.

If however α = 2 then

1 > (1 − \frac{1}{5^{β+1}} ) (1 − \frac{1}{13^{γ+1}} ) = \frac{55296}{54925} > 1

so there is no solution. Hence we can assume β = 1 and start again setting n = 3^{α}5^{1}13^{γ}. Then

1 > (1 − \frac{1}{3^{α+1}} ) (1 − \frac{1}{13^{γ+1}} ) = \frac{512}{507} > 1

so indeed there is no solution with β = 1 for any α ≥ 1 or γ ≥ 1 in this case, so we have exhausted all possibilities.

We find many elements of R_{4} which are even with ω(n) = 3. For example

418 = 2·11·19, 3596 = 2^{2}·29·31, 3956 = 2^{2}·23·43, 5396 = 2^{2}·19·71, 8636 = 2^{2}·17·127, ….

Each of the solutions we have found has the shape n = 2^{e} · p · q where e ≥ 1 and p < q are odd primes. See the comments on this case in the Introduction. The form 2^{e}p_{1} ⋯ p_{m}, where he p_{i} are distinct odd primes, appears to be a sensible place to start when seeking an infinite number of solutions to ϕ(n) | σ(n).

5 Properties of R_{5}

Lemma 15. If n ∈ R_{5} has ω(n) = 3 then n ∈ {190, 812, 1672, 56252}.

Proof. By Corollary 5 we must have n even. We now show that 3 ∤ n. Assume 3 | n and let n = p_{1}^{α_{1}}p_{2}^{α_{2}}p_{3}^{α_{3}} with different primes p_{1}, p_{2} and p_{3}. There are at least one or at most two h(p_{i}^{α_{i}}) > 5^{1/3} with i = 1, 2, 3. We also know that if h(p_{i}^{α_{i}}) > 5^{1/3}, then p_{i} ∈ {2, 3}. But h(p_{i}^{α_{i}}) is increasing by α_{i} and decreasing by p_{i}, so if both 2 | n and 3 | n, then 6 < h(2)h(3)h(p_{3}^{α_{3}}) ≤ h(2^{α_{1}})h(3^{α_{2}})h(p_{3}^{α_{3}}) = 5, which is false. So 3 ∤ n.

Let n = 2^{α}p^{β}q^{γ} with p, q odd primes and α, β, and γ positive integers. By Equation (3), we have

\frac{1}{\sqrt{5}} > (1 − \frac{1}{2}) (1 − \frac{1}{p}) (1 − \frac{1}{q})

which implies p < 19, so p ∈ {5, 7, 11, 13, 17}. We treat these possibilities in three cases.

(1) n = 2^{α}5^{β}q^{γ} with q > 5: Firstly

1 − \frac{1}{2^{α+1}} = \frac{5/4}{h(q^{γ})h(5^{β})} < \frac{5}{6} ⟹ α = 1.

Then using this value for α we get by Equation (2)

\frac{3}{4} (1 − \frac{1}{5^{β+1}} ) (1 − \frac{1}{q^{γ+1}} ) = \frac{4}{5} (1 − \frac{1}{q})^{2}

so thus

(1 − \frac{1}{5^{β+1}} ) (1 − \frac{1}{q^{γ+1}} ) = \frac{16}{15} (1 − \frac{1}{q})^{2} < 1.

Thus q < 32 so we use Algorithm A for each value of q with 7 ≤ q ≤ 31 to get the solution 2 · 5 · 19 = 190.

(2) n = 2^{α}7^{β}q^{γ}. The same method used for (1) shows α ∈ {1, 2}. Then taking each of these separately leads to q ≤ 7 in case α = 1 and q ≤ 41 in case α = 2. Using Algorithm A, from the first we obtain no solution and from the second 2^{2} · 7 · 29 = 812 and 2^{2} · 7^{3} · 41 = 56252

(3) Let n = 2^{α}p^{β}q^{γ} with 11 ≤ p ≤ 17. Then Equation (3) implies

q ∈ {13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61}.

Using Algorithm A we obtain the solution 2^{3} · 11 · 19 = 1672.

6 Larger values of a

Lemma 16. If a ≥ 5 and n ∈ R_{a} and ω(n) = 3 then n is even. If a ≥ 15 then R_{a} = ∅.

Proof. The first part follows from Corollary 5. By Equation (3), if n ∈ R_{a} has the form n = 2^{u}p^{v}q^{w} we have

0.259 ≥ \frac{1}{\sqrt{15}} > (1 − \frac{1}{2}) (1 − \frac{1}{p}) (1 − \frac{1}{q}) ≥ (1 − \frac{1}{2}) (1 − \frac{1}{3}) (1 − \frac{1}{5}) > 0.266,

so there is no such n.

Using Equation (3) we get:

Lemma 17. Let n ∈ R_{a} have ω(n) = 3. If a ≥ 9 then 3 | n. If a ≥ 7 then 3 or 5 divides n. If a ≥ 10 and n = 2^{u}3^{v}q^{w} then q < 1/(1 − 3/\sqrt{a}).

It follows that

• a = 10 ⟹ q ∈ {5, 7, 11, 13, 19},

• a = 11 ⟹ q ∈ {5, 7},

• a = 12 ⟹ q ∈ {5, 7},

• a = 13 ⟹ q = 5, and

• a = 14 ⟹ q = 5.

Using these constraints and Algorithm A leads to Lemma 18. If n ∈ R_{a} has ω(n) = 3 then

a = 10 ⟹ n ∈ {168, 270, 2376},
a = 13 ⟹ n = 27000,

and R_{11} = R_{12} = R_{14} = ∅.

The following well known result [1, 2, 4] guarantees the existence of primitive prime divisors for expressions of the form a^{n} − 1 with fixed a > 1.

Lemma 19. Let a and n be integers greater than 1. Then there exists a prime p | a^{n} − 1 which does not divide any of a^{m} − 1 for each m ∈ {2, …, n − 1}, except possibly in the two cases n = 2 and a = 2^{β} − 1 for some β ≥ 2, or n = 6 and a = 2. Such a prime is called a primitive prime factor.

The following divisibilities are well known.

Lemma 20. Let p and q > 2 be distinct primes and let e ≥ 1 be given. Let o := ord_{q}p. If o ∤ e + 1 then ν_{q}(σ(p^{e})) = 0. If o | e + 1 then

ν_{q}(σ(p^{e})) = ν_{q} (\frac{p^{o} − 1}{p − 1}) + ν_{q} (\frac{e + 1}{o}) .

If p is an odd prime and e an odd integer then

ν_{2}(σ(p^{e})) = ν_{2} ((p + 1) (\frac{e + 1}{2})) .

If e is even then ν_{2}(σ(p^{e})) = 0.

Lemma 21. If n ∈ R_{9} with ω(n) = 3 then n ∈ {30, 264, 61344}.

Proof.

(1) Firstly, since 2 | n and 3 | n we can write, if n = 2^{α}3^{β}q^{γ} with q ≥ 5. Then, by Equation (2)

(1 − \frac{1}{2^{α+1}} ) (1 − \frac{1}{3^{β+1}} ) (1 − \frac{1}{q^{γ+1}} ) = (1 − \frac{1}{q})^{2}  (6)

We claim

\frac{2^{α+1}3^{β+1}}{2^{α+1} + 3^{β+1} − 1} < q < 2\frac{2^{α+1}3^{β+1}}{2^{α+1} + 3^{β+1} − 1}.  (7)

The upper bound follows from Equation (6) since it implies

(1 − \frac{1}{2^{α+1}} ) (1 − \frac{1}{3^{β+1}} ) > (1 − \frac{1}{q})^{2} > 1 − \frac{2}{q},

and the lower bound by noticing (1 − 1/q^{γ+1}) > (1 − 1/q) leads to

(1 − \frac{1}{2^{α+1}} ) (1 − \frac{1}{3^{β+1}} ) < (1 − \frac{1}{q}) .

(2) Now h(2^{α})h(3^{β})h(q^{γ}) = 9 and 6 = h(2)h(3) ≤ 9/h(q^{γ}) implies h(q^{γ}) ≤ 3/2 = h(5). We get the solution n = 2 · 3 · 5 = 30 so can assume q ≥ 7.

Assume in (3) and (4) that γ = 1.

(3) We will show that α is odd. Equation (2) implies

(2^{α+1} + 3^{β+1} − 1)(q + 1) = 2^{α+2} · 3^{β+1}.  (8)

Define A := 2^{α+1} + 3^{β+1} − 1 and B := 2^{α+2} · 3^{β+1}. If α were even then 3 ∤ A so A | 2^{α+2} giving 2^{α+1} + 3^{β+1} − 1 = 2^{α+2} or 3^{β+1} − 2^{α+1} = 1, which is Catalan’s equation. Thus β = 1 and α = 2. But Equation (8) gives q = 8 which is false. Hence α is odd.

(4) This same equation tells us that ν_{2}(2^{α+1}) ≠ ν_{2}(3^{β+1} − 1) (since equality would lead to 2^{α+3} | B), and, using the oddity of α, ν_{3}(3^{β+1}) ≠ ν_{3}(2^{α+1} − 1): to see this assume β + 1 = ν_{3}(3^{β+1}) = ν_{3}(2^{α+1} − 1), and recall by Lemma 20 that ν_{3}(A) ≤ β + 1, so β + 1 = ν_{3}(A) and q is a Mersenne prime. Writing 2^{α+1} − 1 = 3^{β+1}η, with 3 ∤ η, and cancelling in Equation (8) gives η + 1 = 2^{α+2−o} = 2^{e} where o is odd and e even. Hence η ≡ 0 (mod 3), which is false.

These two inequalities enable us to employ Lemma 20.

ν_{2}(A) = min (α + 1, 1) if β is even,
ν_{2}(A) = min (α + 1, 3 + ν_{2} (\frac{β + 1}{2})) if β is odd,
ν_{3}(A) = min (β + 1, 1 + ν_{3} (\frac{α + 1}{2})) since α is odd.

Also, for α, β ≥ 1 we have ν_{2}((β + 1)/2) ≤ 3(log β)/2 and ν_{3}((α + 1)/2) ≤ log α. Therefore

A = 2^{α+1} + 3^{β+1} − 1 = 2^{ν_{2}(A)} · 3^{ν_{3}(A)} ≤ 2^{3+3(log β)/2} · 3^{1+log α} = 24 · 2^{3(log β)/2} · 3^{log α}.

It follows from this that α and β are bounded, indeed 1 ≤ α ≤ 7 and 1 ≤ β ≤ 5. Then testing each pair (α, β), which satisfy these bounds, using Equation (8) we get q ∉ ℕ, unless

(α, β) ∈ {(1, 1), (2, 1), (3, 1), (3, 3), (5, 1), (5, 3)}.

Substituting these values in Equation (8), using the explicit values of q from Equation (7), gives (1, 1), (3, 1) and (5, 3) as the only solutions with corresponding values of n being 2 · 3 · 5 = 30, 2^{3} · 3 · 11 = 264, and 2^{5} · 3^{3} · 71 = 61344.

(5) Now let γ > 1 and n = 2^{α}3^{β}q^{γ} with q ≥ 5. As before we have

(2^{α+1} − 1)(3^{β+1} − 1)(q^{γ+1} − 1) = (q − 1)^{2}q^{γ−1}2^{α+1}3^{β+1}.  (9)

By Lemma 19, q^{γ+1} − 1 has a primitive prime factor, p say, which does not divide q^{2} − 1 = (q +1)(q −1), so cannot be 2 or 3 so, by Equation (9), must divide q −1, which is impossible. Hence the case γ > 1 does not arise.

Lemma 22. The solutions to σ(n) = 6 · ϕ(n) with ω(n) = 3 are 616, 79000 and 2^{p−2} · 5 · M_{p} where M_{p} is any Mersenne prime.

Proof.

(1) By Corollary 5 each n ∈ R_{6} is even. If 3 | n let n = 2^{α} · 3^{β} · q^{γ}. Then by Equation (2)

(1 − \frac{1}{2^{2}} ) (1 − \frac{1}{3^{2}} ) (1 − \frac{1}{q^{2}} ) ≤ \frac{2}{3} (1 − \frac{1}{q})^{2}

we get 1 − 1/q^{2} ≤ 1 − 2/q + 1/q^{2}, which is false, so we can also assume 3 ∤ n.

(2) If we also had 5 ∤ n and 7 ∤ n with n = 2^{α}r^{β}q^{γ} then r ≥ 11 and q ≥ 13, r and q being odd primes, then we would get

\frac{1}{\sqrt{6}} > (1 − \frac{1}{2}) (1 − \frac{1}{11}) (1 − \frac{1}{13})

which is false. If 5 | n and 7 | n we get the solution n = 2·5·7 (a Mersenne solution 2^{3−2}·5·M_{3}), and therefore no other solution with both these prime divisors in R_{6}. Hence we can assume 5 | n or 7 | n, but not both.

(3) Now assume 5 ∥ n so n = 2^{α} · 5 · q^{γ}. Therefore

(1 − \frac{1}{2^{α+1}} ) (1 − \frac{1}{5^{2}} ) (1 − \frac{1}{q^{γ+1}} ) = \frac{24}{25} (1 − \frac{1}{q})^{2}

giving

(1 − \frac{1}{2^{α+1}} ) (1 − \frac{1}{q^{γ+1}} ) = (1 − \frac{1}{q})^{2} = 4 (1 − \frac{1}{2})^{2} (1 − \frac{1}{q})^{2}

so m := 2^{α}q^{γ} is in R_{4}. But then, by Lemma 13, we have m = 2^{p−2} · M_{p} for some prime p such that M_{p} is prime. Therefore in this case we get n = 2^{p−2} · 5 · M_{p}.

(4) Now assume 5 ∤ n so we must have n = 2^{α}7^{β}q^{γ} with q ≥ 11. Then

(1 − \frac{1}{2^{α+1}} ) (1 − \frac{1}{7^{β+1}} ) (1 − \frac{1}{q^{γ+1}} ) = \frac{54}{49} (1 − \frac{1}{q})^{2} < 1

giving 1 − 1/q < \sqrt{49/54} so q ∈ \{11, 13, 17, 19\}. Applying Algorithm A we get n = 2^{3} · 7 · 11 as the only solution.

(5) Now we have to consider n = 2^{α}5^{β}q^{γ} with β ≥ 2. We can write

1 − \frac{1}{2^{α+1}} = \frac{6}{h(5^{β})h(q^{γ})} (1 − \frac{1}{2})^{2} ≤ \frac{6}{4h(5^{2})h(q)} < \frac{30}{31}

so 2^{α+1} < 31 giving α ∈ {1, 2, 3}. We consider each of these possibilities. If α = 1 we get

(1 − \frac{1}{5^{β+1}} ) (1 − \frac{1}{q^{γ+1}} ) = \frac{96}{75} (1 − \frac{1}{q})^{2} < 1

giving the single solution q = 7. Algorithm A gives n = 2 · 5 · 7 only.

If α = 2 or α = 3 a similar argument gives an explicit bound for q (7 ≤ q ≤ 19 and 7 ≤ q ≤ 83 respectively), and then using Algorithm A we obtain just one new solution with α = 3, namely n = 2^{3} · 5^{3} · 79 = 79000.

Lemma 23. The solutions to σ(n) = 7 · ϕ(n) with ω(n) = 3 are 78, 140, 2214, and 25758.

Proof.

(1) By Corollary 5 we get n even, and by Lemma 17 we have 3 | n or 5 | n. If 15 | n then

9 = h(2 · 3 · 5) ≤ 7

so exactly one of 3 and 5 divides n.

(2) Let 3 | n so we can write n = 2^{α}3^{β}q^{γ} with q ≥ 7. Then

(1 − \frac{1}{2^{α+1}} ) (1 − \frac{1}{3^{2}} ) (1 − \frac{1}{7^{2}} ) ≤ \frac{7}{9} (1 − \frac{1}{q})^{2} < \frac{7}{9}

so therefore 1 − 1/2^{α+1} < 343/384 giving α ∈ {1, 2}.

(3) If 3 | n and α = 1 then

(1 − \frac{1}{3^{β+1}} ) (1 − \frac{1}{q^{γ+1}} ) = \frac{28}{27} (1 − \frac{1}{q})^{2} < 1

so, from this last inequality q < 56 and so 7 ≤ q ≤ 53. Algorithm A then gives the solutions n = 2 · 3 · 13 = 78, n = 2 · 3^{3} · 41 = 2214 and n = 2 · 3^{5} · 53 = 25758.

(4) If however 3 | n and α = 2 then

(1 − \frac{1}{3^{β+1}} ) (1 − \frac{1}{7^{2}} ) ≤ \frac{8}{9} (1 − \frac{1}{q})^{2} < \frac{8}{9}

which gives β = 1. But then, by Equation (1), h(q^{γ}) = 1 which is false for all primes q and integers γ ≥ 1.

(5) If 5 | n and q ≥ 19 then

\frac{1}{\sqrt{7}} > (1 − \frac{1}{2}) (1 − \frac{1}{5}) (1 − \frac{1}{19})

which is false, so q ∈ {7, 11, 13, 17} and using Algorithm A we get n = 2^{2} · 5 · 7 = 140.

Lemma 24. The solutions to σ(n) = 8 · ϕ(n) with ω(n) = 3 are 594, 7668 and 2^{p−2} · 3 · M_{p} where M_{p} is any Mersenne prime.

Proof.

(1) By Corollary 5 we get n even. If 3 ∤ n then n = 2^{α}r^{β}q^{γ} with r ≥ 5. If q ≥ 11 we contradict Equation (3), so we must then have q = 7 and r = 5. But then Algorithm A gives no solutions in R_{8} for n of the form n = 2^{α}5^{β}7^{γ}, so all solutions in R_{8} must have 3 | n.

(2) Now suppose that 3 ∥ n so n = 2^{α}3^{1}q^{γ}. Substitute this value in Equation (2) to get

(1 − \frac{1}{2^{α+1}} ) (1 − \frac{1}{q^{γ+1}} ) = (1 − \frac{1}{q})^{2} .

As we saw in the case for R_{4}, the solutions to this equation are precisely m = 2^{p−2} · M_{p}, where M_{p} is any Mersenne prime. This shows all solutions to σ(n) = 8ϕ(n) with ω(n) = 3 and 3 ∥ n are of the form n = 2^{p−2} · 3 · M_{p}.

(3) Now consider n = 2^{α}3^{β}q^{γ} with β ≥ 2 and q ≥ 5. Then

(1 − \frac{1}{2^{α+1}} ) (1 − \frac{1}{3^{β+1}} ) (1 − \frac{1}{q^{γ+1}} ) = \frac{8}{9} (1 − \frac{1}{q})^{2} .

Therefore

(1 − \frac{1}{2^{α+1}} ) (1 − \frac{1}{3^{3}} ) ≤ \frac{8}{9h(q^{γ})} < \frac{8}{9}.

So 1 − 1/2^{α+1} < 12/13 giving α ∈ {1, 2}.

(4) If α = 2 then

(1 − \frac{1}{3^{β+1}} ) (1 − \frac{1}{q^{γ+1}} ) = \frac{64}{63} (1 − \frac{1}{q})^{2} < 1

so q < 1/(1 − \sqrt{63/64}) < 128 giving 5 ≤ q ≤ 127.

(5) If however α = 1, using this same approach leads to q < 1/(1 − \sqrt{27/32}) < 12.3 and so q ∈ {5, 7, 11}. Therefore, no matter what the value of α, we must have 5 ≤ q ≤ 127. Then, using Algorithm A for n of the form 2^{α}3^{β}q^{γ} for each such q we get, other than the Mersenne solutions in this range, n = 2 · 3^{3} · 11 = 594 and n = 2^{2} · 3^{3} · 71 = 7668 only.

Summarizing all of these results:

Theorem 25. Excluding the case σ(n)/ϕ(n) = 4 and n even, there are a finite number of solutions to ϕ(n) | σ(n) with ω(n) ≤ 3 if and only if there are a finite number of Mersenne primes and a finite number of primes of the form 2 · 3^{α} − 1. These solutions are determined explicitly:

{2, 3, 15, 30, 78, 140, 168, 190, 264, 270, 594, 616, 812, 1485,
1672, 2214, 2376, 5049, 7668, 25758, 27000, 56252, 61344, 79000},

and

{2^{p−2} · M_{p}, 2^{p−2} · 3 · M_{p}, 2^{p−2} · 5 · M_{p}, 3^{α} · 7 · N_{α+1}}

where M_{p} is any Mersenne prime 2^{p} − 1 and N_{a} is any prime of the form 2 · 3^{a} − 1.

7 Generating large elements of R_{2}

The reader will recall Lemma 13 where a potentially infinite parametrized set of elements of R_{4} was characterized, namely 2^{p−2}M_{p} where M_{p} is the Mersenne prime at prime p. There are examples of related solutions to σ(n) = a · ϕ(n) for other values of a:

(1) Every n = 2^{p−2} · 5 · M_{p}, where M_{p} := 2^{p} − 1 is prime, is in R_{6}.

(2) Every n = 2^{p−2} · 3 · M_{p}, where M_{p} := 2^{p} − 1 is prime with p ≥ 5, is in R_{8}. More generally, if an odd number m ∈ R_{a} and odd prime number p with M_{p} prime has M_{p} ∤ m, then m · 2^{p−2} · M_{p} ∈ R_{4a}.

(3) If n ∈ R_{2} with n > 3 then 3n ∈ R_{4}. More generally, if n ∈ R_{a} and a prime p ∤ n with σ(p) · a = b · ϕ(p) then pn ∈ R_{b}.

Using (1), (2) and (3) we can generate some large elements of R_{a} with increasing a. However, we observe large squarefree elements with bounded a, for example in R_{2}, and here describe a method for generating them.

Consider the identity

(\frac{2m + 2}{2m}) (\frac{2m + 4}{2m + 2}) (\frac{2m + 6}{2m + 4}) ⋯ (\frac{4m − 2}{4m − 4}) (\frac{4m}{4m − 2}) = 2.

Denote 2m, 2m + 2, ⋯, 4m − 2 as n_{1}, n_{2}, ⋯, n_{m}. Let p_{i} := n_{i} + 1. Each p_{i} which is an odd prime is retained as a prime divisor of n. The remaining prime divisors are found by modular relationships after cancellation.

For example m = 6, then from the above equation we get

(\frac{14}{12}) (\frac{16}{14}) (\frac{18}{16}) (\frac{20}{18}) (\frac{22}{20}) (\frac{24}{22}) = 2.

Consequently, we have p_{1} = 13; p_{3} = 17; p_{4} = 19; p_{6} = 23. After cancellation, we obtain,

(\frac{7 · 5}{2^{2} · 11}) (\frac{p_{2} + 1}{p_{2} − 1}) (\frac{p_{5} + 1}{p_{5} − 1}) = 1.

Trying 2^{2} · 11 | p_{2} + 1, if p_{2} = 43, then p_{5} = 11. Finally, we discover a solution n = 11 · 13 · 17 · 19 · 23 · 43 = 45680921.

Another example m = 10. From

(\frac{22}{20}) (\frac{24}{22}) (\frac{26}{24}) (\frac{28}{26}) (\frac{30}{28}) (\frac{32}{30}) (\frac{34}{32}) (\frac{36}{34}) (\frac{38}{36}) (\frac{40}{38}) = 2,

we can get p_{2} = 23; p_{5} = 29; p_{6} = 31; p_{9} = 37. After cancelling, we get

(\frac{8 · 19}{11 · 7 · 3}) (\frac{p_{1} + 1}{p_{1} − 1}) (\frac{p_{3} + 1}{p_{3} − 1}) (\frac{p_{4} + 1}{p_{4} − 1}) (\frac{p_{7} + 1}{p_{7} − 1}) (\frac{p_{8} + 1}{p_{8} − 1}) (\frac{p_{10} + 1}{p_{10} − 1}) = 1.

Let 11 | p_{1} + 1, trying p_{1} = 43 and simplifying again, let 21 | p_{3} + 1, trying p_{3} = 41. Using the similar method to try the same equation, 4 | p_{4} − 1, choose p_{4} = 17. Trying 14 | p_{7} + 1, taking p_{7} = 13. Trying 4 | p_{8} + 1, taking p_{8} = 47, then p_{10} = 229. Now we are able to discover a solution n = 13 · 17 · 23 · 29 · 31 · 37 · 41 · 43 · 47 · 229 = 3208242429090101.

This procedure appears to have algorithmic content, and may enable squarefree solutions to σ(n) = 2ϕ(n) to be found with ω(n) arbitrarily large. Examples up to ω(n) = 10 are given in Table 3.

\begin{matrix}ω(n) & n & factors \\ 1 & 3 & 3 \\ 2 & 35 & 5 · 7 \\ 3 & 1045 & 5 · 11 · 19 \\ 4 & 24871 & 7 · 11 · 17 · 19 \\ 5 & 1390753 & 7 · 13 · 17 · 29 · 31 \\ 6 & 45680921 & 11 · 13 · 17 · 19 · 23 · 43 \\ 7 & 30805485137 & 7 · 17 · 19 · 23 · 31 · 97 · 197 \\ 8 & 153068460649 & 13 · 17 · 19 · 23 · 29 · 31 · 41 · 43 \\ 9 & 1200381343577759 & 7 · 19 · 23 · 29 · 31 · 41 · 131 · 181 · 449 \\ 10 & 3208242429090101 & 13 · 17 · 23 · 29 · 31 · 37 · 41 · 43 · 47 · 229 \end{matrix}

Table 3: Squarefree solutions to σ(n) = 2 · ϕ(n).

8 Acknowledgment

The authors wish to express their gratitude to a referee who corrected errors in an earlier version of this paper and made other helpful suggestions.

References

[1] A. S. Bang, Taltheoretiske undersogelser, Tidsskrift for Mat. 5 (1886), 70–80, 130–137.

[2] G. D. Birkhoff and H. S. Vandiver, On the integral divisors of a^{n} − b^{n}, Ann. of Math. 5 (1904), 173–180.

[3] K. A. Broughan and D. Delbourgo, On the ratio of the sum of divisors and Euler’s totient function I, J. Integer Seq. 16 (2013), Article 13.8.8.

[4] M. Roitman, On Zsigmondy primes, Proc. Amer. Math. Soc. 125 (1997), 1913–1919.

[5] B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94.

[6] S. S. Wagstaff, Divisors of Mersenne numbers, Math. Comp. 40 (1983), 385–397.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11A41, 54H99, 11N60, 11N25, 11N64. Keywords: sum of divisors, Euler’s totient function.

(Concerned with sequence \underline{A000010}, \underline{A000043}, \underline{A000203}, \underline{A000668}, \underline{A003307}, \underline{A062699}, \underline{A068390}, \underline{A079363}, and \underline{A104901}.)

Received October 31 2013; revised version received August 4 2014. Published in Journal of Integer Sequences, August 12 2014.

Return to Journal of Integer Sequences home page.