On Integers for Which the Sum of Divisors is the Square of the Squarefree Core

Kevin A. Broughan Department of Mathematics

University of Waikato

Private Bag 3105 Hamilton, New Zealand

kab@waikato.ac.nz

Jean-Marie De Koninck

Départment de mathématiques et de statistique Université Laval Québec G1V 0A6

Canada

jmdk@mat.ulaval.ca

Imre Kátai

Department of Computer Algebra

Pázmány Péter sétány I/C

H-1117 Budapest

Hungary

katai@compalg.inf.elte.hu

Florian Luca

Centro de Ciencias Matemáticas Universidad Nacional Autonoma de México

C. P. 58089 Morelia, Michoacán

México

fluca@matmor.unam.mx

Abstract

We study integers n > 1 satisfying the relation σ(n) = γ(n)^{2}, where σ(n) and γ(n) are the sum of divisors and the product of distinct primes dividing n, respectively. We show that the only solution n with at most four distinct prime factors is n = 1782. We show that there is no solution which is fourth power free. We also show that the number of solutions up to x > 1 is at most x^{1/4+ϵ} for any ϵ > 0 and all x > x_{ϵ}. Further, call n primitive if no proper unitary divisor d of n satisfies σ(d) | γ(d)^{2}. We show that the number of primitive solutions to the equation up to x is less than x^{ϵ} for x > x_{ϵ}.

1 Introduction

At the Western Number Theory conference in 2000, the second author asked for all positive integer solutions n to the equation

σ(n) = γ(n)^{2}  (1)

(denoted “De Koninck’s equation”), where σ(n) is the sum of all positive divisors of n, and γ(n) is the product of the distinct prime divisors of n, the so-called “core” of n. It is easy to check that n = 1 and n = 1782 are solutions, but, as of the time of writing, no other solutions are known. A computer search for all n ≤ 10^{11} did not reveal any other solution. The natural conjecture (coined the “De Koninck’s conjecture”) is that there are no other solutions. It is included in Richard Guy’s compendium [1, Section B11].

It is not hard to see, and we prove such facts shortly, that any non-trivial solution n must have at least three prime factors, must be even, and can never be squarefree. The fourth author [2] has a derivation that the number of solutions with a fixed number of prime factors is finite. Indeed, he did this for the broader class of positive solutions n to the equation σ(n) = aγ(n)^{K} where K ≥ 2 and 1 ≤ a ≤ L with K and L fixed parameters. Other than this, there has been little progress on De Koninck’s conjecture.

Here, we show that the above solutions n = 1, 1782 are the only ones having ω(n) ≤ 4. As usual, ω(n) stands for the number of distinct prime factors of n. The method relies on elementary upper bounds for the possible exponents of the primes appearing in the factorization of n and then uses resultants to solve the resulting systems of polynomial equations whose unknowns are the prime factors of n.

We then show that if an integer n is fourth power free (i.e. p^{4} ∤ n for all primes p), then n cannot satisfy De Koninck’s equation (1). We then count the number of potential solutions n up to x. Pollack and Pomerance [4], call a positive integer n to be prime–perfect if n and σ(n) share the same set of prime factors. Obviously, any solution n to the De Koninck’s equation is also prime–perfect. Pollack and Pomerance show that the set of prime–perfect numbers is infinite and the counting function of prime–perfects n ≤ x has cardinality at most x^{1/3+o(1)} as x → ∞. By using the results of Pollack and Pomerance, we show that the number of solutions n ≤ x to De Koninck’s equation is at most x^{1/4+ϵ} for any ϵ > 0 and all x > x_{ϵ}.

By restricting to so-called “primitive” solutions, using Wirsing’s method [5], we obtain an upper bound of O(x^{ϵ}) for all ϵ > 0. The notion of primitive that is used is having no proper unitary divisor d | n satisfying σ(d) | γ(d)^{2}. In a final section of comments, we make some remarks about the related problem of identifying those integers n such that γ(n)^{2} | σ(n).

In summary: the aim of this paper is to present items of evidence for the truth of De Koninck’s conjecture, and to indicate the necessary structure of a possible counter example.

Any non-trivial solution other than 1782 must be even, have one prime divisor to power 1 and possibly one prime divisor to a power congruent to 1 modulo 4, with other odd prime divisors being to even powers. At least one prime divisor must appear with an exponent 4 or more. Finally, any counter example must be greater than 10^{11}.

We use the following notations, most of which have been recorded already: σ(n) is the sum of divisors, γ(n) is the product of the distinct primes dividing n, if p is prime v_{p}(n) is the highest power of p which divides n, ω(n) is the number of distinct prime divisors of n, and K is the set of all solutions to σ(n) = γ(n)^{2}. The symbols p, q, p_{i} and q_{i} with i = 1, 2, … are reserved for odd primes.

2 Structure of solutions

First we derive the shape of the members of K.

Lemma 1. If n > 1 is in K, then

n = 2^{e}p_{1} ∏_{i=2}^{s} p_{i}^{a_{i}},

where e ≥ 1 and a_{i} is even for all i = 3, …, s. Furthermore, either a_{2} is even in which case p_{1} ≡ 3 (mod 8), or a_{2} ≡ 1 (mod 4) and p_{1} ≡ p_{2} ≡ 1 (mod 4).

Proof. Firstly, we note that n must be even: indeed, if n > 1 satisfies σ(n) = γ(n)^{2} and n is odd, then σ(n) must be odd so that the exponent of each prime dividing n must be even, making n a perfect square. But then n < σ(n) = γ(n)^{2} ≤ n, a contradiction.

Secondly, since n is even, it follows that 2^{2}∥γ(n)^{2}. Write

n = 2^{e} ∏_{i=1}^{s} p_{i}^{a_{i}}

with distinct odd primes p_{1}, …, p_{s} and positive integer exponents a_{1}, …, a_{s}, where the primes are arranged in such a way that the odd exponents appear at the beginning and the even ones at the end. Using the fact that σ(2^{e}) = 2^{e+1}−1 is odd, we get that 2^{2}∥ ∏_{i=1}^{s} σ(p_{i}^{a_{i}}). Thus, there are at most two indices i such that σ(p_{i}^{a_{i}}) is even, with all the other indices being odd. But if p is odd and σ(p^{a}) is also odd, then a is even. Thus, either only a_{1} is odd, or only a_{1} and a_{2} are odd. Now let us show that there is at least one exponent which is 1. Assuming that this is not so, the above argument shows that a_{1} ≥ 3 and that a_{i} ≥ 2 for i = 2, …, s. Thus,

4p_{1}^{2} ∏_{i=2}^{s} p_{i}^{2} = γ(n)^{2} = σ(n) ≥ σ(2)σ(p_{1}^{3}) ∏_{i=2}^{s} σ(p_{i}^{2}) > 3p_{1}^{3} ∏_{i=2}^{s} p_{i}^{2},

leading to p_{1} < 4/3, which is impossible. Hence, a_{1} = 1. Finally, if a_{2} is even, then 2^{2}∥σ(p_{1}) showing that p_{1} ≡ 3 (mod 8), while if a_{2} is odd, then 2∥σ(p_{1}) and 2∥σ(p_{2}^{a_{2}}), conditions which easily lead to the conclusion that p_{1} ≡ p_{2} ≡ 1 (mod 4) and a_{2} ≡ 1 (mod 4).

3 Solutions with ω(n) ≤ 4

Theorem 2. Let n ∈ K with ω(n) ≤ 4. Then n = 1 or n = 1782.

Proof. Using Lemma 1, we write n = 2^{α}pm, where α > 0 and m is coprime to 2p.

We first consider the case p = 3. If additionally m = 1, we then get that σ(n) = 6^{2}, and we get no solution. On the other hand, if m > 1, then σ(m) is a divisor of γ(n)^{2}/4 and must therefore be odd. This means that every prime factor of m appears with an even exponent. Say q^{β}∥m. Then

σ(q^{β}) = q^{β} + ⋯ + q + 1

is coprime to 2q and is larger than 3^{2} + 3 + 1 > 9. Thus, there exists a prime factor of m other than 3 or q, call it r, which divides q^{β} + ⋯ + q + 1, implying that it also divides m and that it appears in the factorization of m with an even exponent. Since ω(n) ≤ 4, we have m = q^{β}r^{γ}. Now

q^{β} + ⋯ + q + 1 = 3^{i}r^{j} and r^{γ} + ⋯ + r + 1 = 3^{k}q^{ℓ},

where i + k ≤ 2 and j, ℓ ∈ {1, 2}. Thus,

(q^{β} + ⋯ + q + 1)(r^{γ} + ⋯ + r + 1) = 3^{i+k}q^{ℓ}r^{j}.

The left–hand side of this equality is greater than or equal to 3q^{β}r^{γ}. In the case where β > 2, we have β ≥ 4, so that q^{4}r^{2} ≤ q^{β}r^{α} ≤ 9q^{2}r^{2}, giving q ≤ 3, which is a contradiction. The same contradiction is obtained if γ > 2.

Thus, β = γ = 2. If l = j = 2, we then get that

(q^{2} + q + 1)(r^{2} + r + 1) = 3^{i+k}q^{2}r^{2},

leading to σ(2^{α}) | 3^{2−i−j}. The only possibility is α = 1 and i + j = 1, showing that i = 0 or j = 0. Since the problem is symmetric, we treat only the case i = 0. In that case, we get q^{2} + q + 1 = r^{2}, which is equivalent to (2q + 1)^{2} + 3 = (2r)^{2}, which has no convenient solution (q, r).

If j = ℓ = 1, we then get that

q^{2}r^{2} < (q^{2} + q + 1)(r^{2} + r + 1) < 9qr,

implying that qr < 9, which is false.

Hence, it remains to consider the case j = 2 and ℓ = 1, and viceversa. Since the problem is symmetric in q and r, we only look at j = 2 and ℓ = 1. In that case, we have

q^{2}r^{2} < (q^{2} + q + 1)(r^{2} + r + 1) = 3^{i+k}r^{2}q,

so that q < 3^{i+k}. Since q > 3, this shows that i = k = 1 and q ∈ {5, 7}. Therefore, r^{2} + r + 1 = 75, 147, and neither gives a convenient solution n.

From now on, we can assume that p > 3, so that p + 1 = 2^{u}m_{1}, where u ∈ {1, 2} and m_{1} > 1 is odd. Let q be the largest prime factor of m_{1}. Clearly, p + 1 ≥ 2q, so that q < p. Moreover, since ω(n) ≤ 4 we have

p < 4q^{4} < q^{6},

so that q > p^{1/6}. Let again β be such that q^{β}∥n. We can show that β ≤ 77. Indeed, assuming that β ≥ 78, we first observe that

p^{13} < q^{78} ≤ q^{β} < σ(q^{β}),

and write

σ(q^{β}) = 2^{v}m_{2},

where v ∈ {0, 1} and m_{2} is coprime to 2q. If m_{2} divides p^{2}, we get that

p^{13} < σ(q^{β}) ≤ 2p^{2},

which is a contradiction. Thus, there exists another prime factor r of n, and m_{2} ≤ p^{2}r^{2}. Hence,

p^{13} < σ(q^{β}) < 2p^{2}r^{2} < p^{3}r^{2},

implying that r > p^{5}. Let γ be such that r^{γ}∥n. Then

r + 1 ≤ σ(r^{γ}) ≤ 2p^{2}q^{2} < p^{5},

which is a contradiction. Thus, β ≤ 77.

Say r doesn’t appear in the factorization of (p + 1)σ(q^{β}). Then we need to solve the system of equations

p + 1 = 2^{u}q^{w} and q^{β} + ⋯ + q + 1 = 2^{v}p^{z},

where β ∈ {1, …, 77}, u ∈ {1, 2}, 0 ≤ v ≤ 2 − u, {w, z} ⊆ {1, 2}, which we can solve with resultants. This gives us a certain number of possibilities for the pair (p, q). If ω(n) = 3, we have σ(n) = 4p^{2}q^{2}, and we find n. If ω(n) = 4, then σ(r^{γ}) is a divisor of 2p^{2}q^{2} and we find certain possibilities for the pair (r, γ). Then we extract n from the relation σ(n) = 4p^{2}q^{2}r^{2}.

Now say r appears in the factorization of (p + 1)σ(q^{β}). We then write

p + 1 = 2^{u}q^{w}r^{δ}  and σ(q^{β}) = 2^{v}p^{z}r^{η},  (2)

where u ∈ {1, 2}, w ∈ {1, 2}, 0 ≤ v ≤ 2 − u, z ∈ {0, 1, 2}, δ + η ∈ {1, 2}. If z = 0, then since q > p^{1/6}, we have that

q < σ(q^{β}) ≤ 2r^{2} < r^{3},

so that r > q^{1/3} > p^{1/18}. Now γ ≤ 89, for if not, then

p^{5} < r^{90} ≤ r^{γ} < σ(r^{γ}) < 2p^{2}q^{2} < p^{5},

which is false.

Suppose now that z > 0. Then

q^{w}r^{δ} < p < 4q^{w}r^{δ}  (3)

from the first relation of (2), while

\frac{q^{β}}{2r^{η}} < p^{z} < \frac{2q^{β}}{r^{η}}  (4)

from the second relation of (2). If z = 1, we get from (3) and (4) that

r^{δ+η} < 2q^{β−w} and r^{δ+η} > \frac{q^{β−w}}{8} .

From the above left inequality and the fact that δ + η ≥ 1, we read that β − w ≥ 1, and then from the right one that 9r^{2} > 8r^{δ+η} > q^{β−w} ≥ q, and thus r^{2} ≥ 3r > q^{1/2}, so that r > q^{1/4} > p^{1/24}. It now follows easily that γ ≤ 119, for if not, then γ ≥ 120 would give

p^{5} < r^{120} ≤ r^{γ} < σ(r^{γ}) ≤ 2p^{2}q^{2} < p^{5},

which is a contradiction. Finally, if z = 2, we get from (4) that

\frac{q^{β/2}}{\sqrt{2}r^{η/2}} < p < \frac{\sqrt{2}q^{β/2}}{r^{η/2}} ,

which combined with (3) yields

r^{δ+η/2} < \sqrt{2}q^{β/2−w} and r^{δ+η/2} > \frac{q^{β/2−w}}{4\sqrt{2}} .

From the above left inequality and because δ + η/2 ≥ 1/2, we read that β/2 > w, implying that β/2 − w ≥ 1/2. Thus,

4\sqrt{2}r^{2} ≥ 4\sqrt{2}r^{δ+η/2} > q^{β/2−w} ≥ q^{1/2}

and therefore

r^{8} > 32r^{4} ≥ (4\sqrt{2}r^{δ+η/2})^{2} > q > p^{1/6},

showing that r > p^{1/48}. This shows that γ ≤ 239, for if γ ≥ 240, then

p^{5} < r^{240} ≤ r^{γ} < σ(r^{γ}) < 2p^{2}q^{2} < p^{5},

which is a contradiction. Thus, we need to solve

p + 1 = 2^{u}q^{w}r^{δ};
σ(q^{β}) = 2^{v}p^{z}r^{η};
σ(r^{γ}) = 2^{λ}p^{s}q^{t},

where 1 ≤ β ≤ 77, 1 ≤ γ ≤ 239, u ∈ {1, 2}, u + v + λ ≤ 2, 1 ≤ w ≤ 2, w + t ≤ 2, δ + η ∈ {1, 2}, z ∈ {0, 1, 2} and s ∈ {0, 1, 2}. This can be solved with resultants and it gives us a certain number of possibilities for the triplet (p, q, r). From σ(n) = 4p^{2}q^{2}r^{2}, we extract n by solving the equation for α, given p, q and r. Failure to detect an integer value for α means the candidate solution fails. A computer program went through all these steps and confirmed the conclusion of Theorem 2.

4 The case of fourth power free n

Theorem 3. If n > 1 is in K, then n is not fourth power free.

Proof. Let us assume that the result is false, that is, that there exists some n ∈ K which is fourth power free. By Lemma 1 we can write

n = 2^{e}p_{1}p_{2}^{a_{2}} ∏_{i=1}^{k} q_{i}^{2},

where a_{2} ∈ {0, 1}. Let Q = {q_{1}, …, q_{k}}. The idea is to exploit the fact that there exist at most two elements q ∈ Q such that q ≡ 1 (mod 3). If there were three or more such elements, then 3^{3} would divide ∏_{q∈Q} σ(q^{2}) and therefore a divisor of γ(n)^{2}, which is a contradiction.

We begin by showing that k ≤ 8. To see this, let

R = {r ∈ Q : gcd (σ(r^{2}), ∏_{q∈Q} q) = 1} .

Then ∏_{r∈R} σ(r^{2}) divides p_{1}^{2} (if a_{2} = 0) and p_{1}^{2}p_{2}^{2} if a_{2} > 0. It follows that σ(r^{2}) is either a multiple of p_{1} or of p_{2} for each r ∈ R. Since there can be at most two r’s for which σ(r^{2}) is a multiple of p_{1}, and at most two r’s for which σ(r^{2}) is a multiple of p_{2}, we get that #R ≤ 4. When r ∈ Q \ R, we have, since σ(r^{2}) > 9, that σ(r^{2}) = r^{2} + r + 1 is a multiple of some prime q_{i_{r}} > 3 for some q_{i_{r}} ∈ Q. Now, since q_{i_{r}} is a prime divisor of r^{2} + r + 1 larger than 3, it must satisfy q_{i_{r}} ≡ 1 (mod 3). Since i_{r} can take the same value for at most two distinct primes r, and there are at most two distinct values of the index i_{r}, we get that k − #R ≤ 4, which implies that k ≤ 8, as claimed.

Next rewrite the equation σ(n) = γ(n)^{2} as

(\frac{2^{e+1} − 1}{4}) ∏_{i=1}^{k} (\frac{q_{i}^{2} + q_{i} + 1}{q_{i}^{2}}) = (\frac{p_{1}^{2}}{p_{1} + 1}) (\frac{p_{2}^{2δ_{2}}}{σ(p_{2}^{a_{2}})}) ,  (5)

where δ_{2} = 0 if a_{2} = 0 and δ_{2} = 1 if a_{2} > 0. The left–hand side of (5) is at most

(\frac{2^{e+1} − 1}{4}) ( ∏_{q≤23} \frac{q^{2} + q + 1}{q^{2}}) < 0.73(2^{e+1} − 1).  (6)

First assume that a_{2} = 0. Then the right–hand side of (5) is

\frac{p_{1}^{2}}{p_{1} + 1} ≥ \frac{9}{4} = 2.25.  (7)

If e = 1, then the left–hand side of inequality (5) is, in light of (6), smaller than 0.73(2^{2}−1) < 2.22, which contradicts the lower bound provided in (7). Thus, e ∈ {2, 3}, and

\frac{p_{1}^{2}}{p_{1} + 1} ≤ 0.73(2^{4} − 1) = 10.95,

so that p_{1} ≤ 11. Since p_{1} ≡ 3 (mod 8), we get that p_{1} ∈ {3, 11}. If p_{1} = 11, then 3 ∈ Q. If p_{1} = 3, then since e ∈ {2, 3}, we get that either 5 or 7 is in Q.

If 3 ∈ Q, then 13 | 3^{2} + 3 + 1, 61 | 13^{2} + 13 + 1 and 97 | 61^{2} + 61 + 1 are all three in Q and are congruent to 1 modulo 3, a contradiction.

If 5 ∈ Q, then 31 | 5^{2} + 5 + 1, 331 | 31^{2} + 31 + 1 and 7 | 331^{2} + 331 + 1 are all in Q, a contradiction.

If 7 ∈ Q, then 7, 19 | 7^{2} + 7 + 1 and 127 | 19^{2} + 19 + 1 are all in Q, a contradiction. Assume next that a_{2} > 0. Then, by Lemma 1, p_{1} ≡ p_{2} ≡ 1 (mod 4). Since e ∈ {1, 2, 3},

it follows that one of 3, 5, 7 divides n.

If 3 | n, then 3 ∈ Q.

If 5 | n, and 5 is one of p_{1} or p_{2}, then 3 | σ(p_{1}p_{2}^{a_{2}}) | n, while if 5 ∈ Q, then 31 = 5^{2} + 5 + 1 is not congruent to 1 modulo 4 and divides n, implying that it belongs to Q, and thus 3 | 31^{2} + 31 + 1 | n.

Finally, if 7 | n, then 7 cannot be p_{1} or p_{2}, meaning that 7 is in Q and therefore that 3 | 7^{2} + 7 + 1, which implies that 3 | n.

To sum up, it is always the case that when a_{2} > 0, necessarily 3 divides n.

Hence, 13 = 3^{2} + 3 + 1 divides n, so that either 13 ∈ Q, or not. If 13 ∉ Q, then 7 | 13 + 1 is in Q, in which case 19 | 7^{2} +7+1 divides n and it is not congruent to 1 modulo 4, implying that 19 ∈ Q and thus that 127 | 19^{2} +19+1 divides n and is not congruent to 1 modulo 4, so that 127 ∈ Q. Hence, all three numbers 7, 19, 127 are in Q, which again is a contradiction.

If 13 ∈ Q, then 61 | 13^{2} + 13 + 1 divides n.

If 61 is one of p_{1} or p_{2}, then 31 | σ(p_{1}p_{2}^{a_{2}}) and 31 ≡ 3 (mod 4), so that 31 ∈ Q. Next 331 | 31^{2} + 31 + 1 is a divisor of n and it is not congruent to 1 modulo 4, implying that it belongs to Q and therefore that 13, 31, 331 are all in Q, a contradiction.

Finally, if 61 ∈ Q, then 97 | 61^{2} +61+1 is a divisor of n. If 97 ∈ Q we get a contradiction since 13 and 61 are already in Q, while if 97 is one of p_{1} or p_{2}, then 7 | σ(p_{1}p_{2}^{a_{2}}) is a divisor of n and therefore necessarily in Q, again a contradiction.

5 Counting the elements in K ∩ [1, x]

Let K(x) = K ∩ [1, x].

Theorem 4. The estimate

#K(x) ≤ x^{1/4+o(1)}

holds as x → ∞.

Proof. By Theorem 1.2 in [4], we have #K(x) = x^{1/3+o(1)} as x → ∞. It remains to improve the exponent 1/3 to 1/4. We recall the following result from [4].

Lemma 5. If σ(n)/n = N/D with (N, D) = 1, then given x ≥ 1 and d ≥ 1

#{n ≤ x : D = d} = x^{o(1)}

as x → ∞.

Now let n ∈ K(x), assume that n > 1 and write it in the form n = A·B with A squarefree, B squarefull and (A, B) = 1. By Lemma 1, we have A ∈ {1, p_{1}, 2p_{1}, p_{1}p_{2}, 2p_{1}p_{2}}. Then

\frac{N}{D} = \frac{σ(n)}{n} = \frac{γ(n)^{2}}{n} = \frac{γ(A)^{2}}{A} · \frac{γ(B)^{2}}{B} = \frac{A}{B/γ(B)^{2}} ,  (8)

and (A, B/γ(B)^{2}) = 1. Since σ(n) > n, it follows that B/γ(B)^{2} < A. Thus,

B/γ(B)^{2} < \sqrt{AB/γ(B)^{2}} ≤ \sqrt{n} ≤ \sqrt{x}.

By Lemma 1 again, we can write B = δC^{2}D, where C is squarefree, D is 4-full, δ ∈ {1, 2^{3}}, and where δ, C and D are pairwise coprime. Then B/γ(B)^{2} = δ/γ(δ)^{2} × D/γ(D)^{2}, so therefore D/γ(D)^{2} ≤ B/γ(B)^{2} < x^{1/2}. Because D is 4-full it follows that D/γ(D)^{2} is squarefull and so the number of choices for D/γ(D)^{2} is O(x^{1/4}). Hence, the number of choices for B/γ(B)^{2} ∈ {D/γ(D)^{2}, 2D/γ(D)^{2}} is also O(x^{1/4}), which together with Lemma 5 and formula (8) implies the desired conclusion.

A positive integer d is said to be a unitary divisor of n if d | n and (d, n/d) = 1; it is said to be a proper unitary divisor of n if it also satisfies 1 < d < n. We will say that an integer n ∈ K(x) is primitive if no proper unitary divisor d of n satisfies σ(d) | γ(d)^{2}. Let us denote this subset of K(x) by H(x). Elements of H(x) can be considered as the primitive solutions of σ(n) = γ(n)^{2}. For example, the number n = 1782 ∈ H(x) since, although the proper divisor d = 6 of n satisfies σ(d) | γ(d)^{2}, it fails to be unitary. Also, it is interesting to observe that the condition σ(d) | γ(d)^{2} seems to be very restrictive: for instance, the only positive integers d < 10^{8} satisfying this condition are 6 and 1782; this is already an indication that the set H(x) is very thin. As a matter of fact, we now prove the following result.

Theorem 6. Let ϵ > 0 be given. Then, given any ϵ > 0,

#H(x) = O(x^{ϵ}).

Proof. Let n ∈ H(x) and assume that x > 0 is large. Let a be the largest divisor of n such that all prime factors p | a satisfy p ≤ log x. Write n = a · b and write down the standard factorization of b into primes as

b = p_{1}^{β_{1}} ⋯ p_{k}^{β_{k}}, where p_{1} < ⋯ < p_{k}.

Set M := ⌈log x/ log log x⌉. Then, since b ≤ n ≤ x and since for each i, we have log x < p_{i}, we get

(log x)^{β_{1}+···+β_{k}} < p_{1}^{β_{1}} ⋯ p_{k}^{β_{k}} = b ≤ x,

implying that

β_{1} + ⋯ + β_{k} < \frac{log x}{log log x}, so that k ≤ M.

Now assume that the positive integer a is given and that there is some positive integer b such that n = a · b is a primitive element of K. We will show how to find b from a using the knowledge of the exponents β_{1}, …, β_{k}.

Firstly, if a is already primitive, we then have b = 1. So, suppose that a is not primitive. Since σ(a)σ(b) = γ(a)^{2}γ(b)^{2}, and the two factors on the right hand side are coprime, we

must have

d := \frac{σ(a)}{(σ(a), γ(a)^{2})} | γ(b)^{2}.

Hence, let p_{1} be the least prime dividing the left–hand side of the above relation. Note that the left–hand side is not 1, since otherwise we would have σ(a) | γ(a)^{2}, which is not possible since n is primitive.

Now replace a by ap_{1}^{β_{1}} and proceed. If at step i < k, we have d = 1, then the choice of the β_{i}’s for i = 1, …, k fails to generate an element of K. We can then move on to the next choice. With success at every step, we generate b from a by finding primes p_{1}, …, p_{k} such that a · p_{1}^{β_{1}} ⋯ p_{k}^{β_{k}} ∈ K.

To complete the proof, we only need to find an upper bound for

#{choices for a} · #{choices for (β_{1}, …, β_{k})},

and this is the same as in Wirsing’s proof [5] or [3, Theorem 7.8, pp. 1008-1010] for the case of multiperfect numbers:

#{choices for (β_{1}, …, β_{k})} ≤ #{(β_{1}, …, β_{k}) : β_{1} + ⋯ + β_{k} ≤ M} ≤ 2^{M},
#{choices for a} ≤ #{n ≤ x : p | n ⇒ p ≤ log x}
≤ #\{n ≤ x : p | n ⇒ log^{\frac{3}{4}} x < p ≤ log x\}
×#\{n ≤ x : p | n ⇒ p ≤ log^{\frac{3}{4}} x\}
≤ 2^{4M} × 2^{M} = 2^{5M},

in which case we obtain the upper bound

2^{6M} = x^{\frac{6 log 2}{log log x}} = x^{o(1)} as x → ∞,

for the number of primitive n ∈ K(x), which completes the proof of this theorem.

6 Final remarks

Here, we briefly consider another question related to the problem of De Koninck, namely the one which consists in identifying those integers n satisfying γ(n)^{2} | σ(n). There is an infinite set of solutions n = 2^{i}3^{j} with i ≡ 5 (mod 6), j ≡ 1 (mod 2). If n = 2^{i}3^{j} satisfies γ(n)^{2} | σ(n), then these two congruence conditions are also satisfied.

Indeed, first let i = 5+6k, j = 1+2m and n = 2^{i}3^{j}. Then σ(2^{i}) = 2^{6(k+1)}−1 ≡ 0 ( mod 9) and 3^{2(m+1)} − 1 ≡ 0 (mod 8) so that 3^{2} | σ(2^{i}) and 2^{2} | σ(3^{j}).

Now assume that n = 2^{i}3^{j} and that the integers r and s are such that 2^{2} | σ(3^{s}) and 3^{2} | σ(2^{r}). It is well–known and quite easy to prove by elementary arguments that

v_{2}(σ(3^{s})) + 1 = v_{2}((3 + 1)(s + 1)) ≥ 3, and
v_{3}(σ(2^{r})) = v_{3}((2 + 1)(r + 1)) ≥ 2,

so by the first of these equations s is odd. By the second equation, we see that r ≡ 2 (mod 3), so that r ≡ 2 (mod 6) or r ≡ 5 (mod 6). If the first of these was true, then r would be even, so that 3 | σ(2^{r}) would not be possible. Thus, we must have r ≡ 5 (mod 6).

Observe that this infinite set 2^{i}3^{j} does not exhaust all of the non-trivial solutions, even those with only two distinct prime factors. For example, n = p^{q−2}q^{p−2} with p = 2, q = 1093 or p = 83, q = 4871 are both solutions, since in either case we have

p^{2} | q^{p−1} − 1 and q^{2} | p^{q−1} − 1,

and such divisibilities yield p^{2}q^{2} | σ(p^{q−2}q^{p−2}). Note also that there are many non-trivial solutions with 3 prime factors, for example 17 solutions up to 10^{6} and 25 up to 4 × 10^{6}. Typical solutions have the form

{2^{3}3^{3}5^{5}, 2^{5}3^{5}7^{1}, 2^{9}3^{4}11^{1}}.

As a final note, let us mention that, given any arbitrary integer k ≥ 2, one can easily check that the more general property γ(n)^{k}|σ(n) is indeed satisfied by infinitely many positive integers n, namely those of the form

n = 2^{2i3^{k−1}−1}3^{j2^{k−1}−1} (i ≥ 1, j ≥ 1).

7 Acknowledgements

Research of F. L. was supported in part by Grant SEP-CONACyT 79685, of I. K. by a grant from the European Union and the European Social Fund and of J-M.D.K. by a grant from NSERC.

References

[1] R. K. Guy, Unsolved Problems in Number Theory, Third Edition, Springer, 2004.

[2] F. Luca, On numbers n for which the prime factors of σ(n) are among the prime factors of n, Result. Math., 45 (2004), 79–87.

[3] C. Pomerance and A. Sárközy, Combinatorial Number Theory, in Handbook of Combinatorics vol I, R. L. Graham, M. Grötschel and L. Lovàsz, eds., Elsevier Science, 1995.

[4] P. Pollack and C. Pomerance, Prime–perfect numbers, INTEGERS, to appear.

[5] E. Wirsing, Bemerkung zu der Arbeit über vollkommene Zahlen, Math. Ann. 137 (1959), 316–318.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11A41. Keywords: sum of divisors, squarefree core of an integer, De Koninck’s conjecture.

Received February 23 2012; revised versions received July 26 2012; August 14 2012; September 3 2012. Published in Journal of Integer Sequences, September 8 2012.

Return to Journal of Integer Sequences home page.