PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 87(101) (2010), 121–128 DOI: 10.2298/PIM1001121D

ON THE COPRIMALITY OF SOME ARITHMETIC FUNCTIONS

Jean-Marie De Koninck and Imre Kátai

Dedicated to Professor Aleksandar Ivić on the occasion of his 60th anniversary

Abstract. Let φ stand for the Euler function. Given a positive integer n, let σ(n) stand for the sum of the positive divisors of n and let τ(n) be the number of divisors of n. We obtain an asymptotic estimate for the counting function of the set {n : gcd(φ(n), τ(n)) = gcd(σ(n), τ(n)) = 1}. Moreover, setting l(n) := gcd(τ(n), τ(n + 1)), we provide an asymptotic estimate for the size of #{n ⩽ x : l(n) = 1}.

1. Introduction

Let φ stand for the Euler function. Given a positive integer n, let σ(n) stand for the sum of the positive divisors of n and let τ(n) be the number of divisors of n. This last function has been extensively studied by A. Ivić in his book on the Riemann Zeta-Function [6].

Given an arithmetical function f and a large number x, examining the number of positive integers n ⩽ x for which gcd(n, f(n)) = 1, has been the focus of several papers. For instance, Paul Erdős [4] established that

#\{n ⩽ x : gcd(n, φ(n)) = 1\} = (1 + o(1))\frac{e^{−γ} x}{logloglogx},

where γ is the Euler constant. A similar result can be obtained if one replaces φ(n) by σ(n). Similarly, letting Ω(n) stand for the number of prime factors of n counting their multiplicity, Alladi [1] proved that the probability that n and Ω(n) are relatively prime is equal to 6/π^{2} by examining the size of {n ⩽ x : gcd(n, Ω(n)) = 1}. Let K(x) stand for the number of positive integers n ⩽ x such that gcd(nτ(n), σ(n)) = 1. Some fifty years ago, Kanold [7] showed that there exist positive constants c_{1} < c_{2} and a positive number x_{0} such that

c_{1} < K(x)/\sqrt{x/ logx} < c_{2} (x ⩾ x_{0}).

2010 Mathematics Subject Classification: 11A05, 11A25, 11N37.

Key words and phrases: Arithmetic functions, number of divisors, sum of divisors.

In 2007, the authors [2] proved that there exists a positive constant c_{3} such that K(x) = c_{3}(1 + o(1))\sqrt{x/logx} (x → ∞). The analogue problem for counting the number of positive integers n for which

(1.1)  gcd(nτ(n), φ(n)) = 1

is trivial. Clearly (1.1) holds for n = 1, 2. But these are the only solutions. Indeed, assume that (1.1) holds for some n ⩾ 3. Then n is squarefree and it must therefore have an odd prime divisor p, in which case 2 | φ(n) and 2 | τ(n), implying that gcd(nτ(n), φ(n)) > 1, thereby proving our claim.

In this paper, we obtain asymptotic estimates for the counting functions

R(x) := #{n ⩽ x : gcd(φ(n), τ(n)) = gcd(σ(n), τ(n)) = 1}
N(x) := #{n ⩽ x : l(n) = 1},

where l(n) := gcd(τ(n), τ(n + 1)).

From here on, gcd(a, b) will be written simply as (a, b). In what follows, we shall denote the logarithmic integral of x by li(x), that is li(x) := ∫_{2}^{x} \frac{dt}{log t}. Moreover, given an integer n ⩾ 2, we shall let ω(n) stand for the number of distinct prime factors of n, with ω(1) = 0. Finally, the letters c_{1}, c_{2}, … will stand for positive constants, while the letters p and q, with or without subscripts, will always stand for prime numbers.

2. Main results

Theorem 1. As x → ∞, we have R(x) = c_{4}(1 + o(1))\frac{x}{\sqrt{log x}}, where c_{4} is a

suitable positive constant.

Theorem 2. As x → ∞, we have N(x) = c_{5}(1 + o(1))\sqrt{x} for some positive

constant c_{5}.

3. Preliminary results

To prove our results we shall need the following lemmas.

Lemma 1. Let f(n) := An^{2} + Bn + C be a primitive polynomial with integer coefficients. Let ρ(m) be the number of solutions of f(n) ≡ 0 (mod m). Let D be the discriminant of f and assume that D ≠ 0. Then ρ is a multiplicative function whose values on the prime powers satisfy

ρ(p^{α}) \{ \begin{matrix}= ρ(p) & if p ∤ D, \\ ⩽ 2D^{2} & if p | D. \end{matrix}

Finally, setting

M_{f} (x, y) := #{n ⩽ x : ∃p > y such thatp^{2}|f(n)},

then

lim_{y→∞} lim sup_{x→∞} \frac{M_{f} (x, y)}{x} = 0.

Proof. For a proof of this result, see Chapter 4 in the book of Hooley [5]. □

Lemma 2. As x → ∞, we have

∑_{m⩽x} |μ(m)| · |μ(m^{2} − 1)| = ξ_{1}(1 + o(1))x,

∑_{m⩽x} |μ(m)| · |μ(m^{2} + 1)| = ξ_{2}(1 + o(1))x,

where ξ_{1} and ξ_{2} are positive constants.

Proof. The proof is a simple application of the Sieve of Eratosthenes and we shall therefore skip it. □

4. The proof of Theorem 1

Let R be the set of those integers n for which

(4.1)  (φ(n), τ(n)) = (σ(n), τ(n)) = 1.

Clearly, we can ignore all solutions of (4.1) which are powers of 2 (namely the even powers of 2). Hence, we only need to consider those solutions n of (4.1) such that p|n for some odd prime p. In this case φ(n) must be even, meaning that τ(n) must be odd, implying that n = u^{2} for some positive integer u. Now, the size of the set of those integers n = u^{2} ⩽ x for which u is a squarefull number and with n satisfying (4.1) is small since it is clearly no larger than cx^{1/4} for some constant c > 0. Ignoring these integers n, we may assume that 3|τ(n) and consequently that 3 does not divide φ(u^{2}) = uφ(u).

Let us now write u = Kv, where K is squarefull and v is squarefree, with (K, v) = 1. Assume that v > 1. Then we have

(φ(n), τ(n)) = (φ(K^{2})φ(v^{2}), 3τ(K^{2})),
(σ(n), τ(n)) = (σ(K^{2})φ(v^{2}), 3τ(K^{2})).

For each squarefull integer K, let R_{K} be the set of those n = u^{2} ∈ R for which u = Kv and let R_{K} (x) = \{n ⩽ x : n ∈ R_{K} \}. It is clear that R_{K} (x) ⩽ \frac{\sqrt{x}}{K}, implying that

(4.2)  ∑_{K>log^{2} x} R_{K} (x) ⩽ \sqrt{x} ∑_{K>log^{2} x} \frac{1}{K} ≪ \frac{\sqrt{x}}{logx}.

It follows from this that we only need to consider those squarefull numbers K ⩽ log^{2} x.

Let n ∈ R_{K}. Then, n = v^{2}K^{2} ⩽ x, where v is a squarefree number whose prime factors are ≡ −1 (mod 3). Hence,

v ⩽ \frac{\sqrt{x}}{K} with ( v, ∏_{\begin{matrix}p⩽\sqrt{x} \\ p≡1 (mod 3) \end{matrix}} p) = 1.

Therefore, by standard sieve techniques, one can easily establish that, for some positive constant c_{6},

(4.3)  R_{K} (x) ⩽ c_{6} \frac{\sqrt{x}}{K\sqrt{logx}} .

Since ∑_{K squarefull} \frac{1}{K} < +∞, it follows from (4.3) that

(4.4)  ∑_{K>y} R_{K} (x) ⩽ o(1) · c_{6} \begin{matrix}√ & \overline{x} \\ √ & \overline{logx} \end{matrix}  (y → ∞)

Let us now estimate R_{K} (x) for a fixed squarefull number K. We separate the different squarefull K’s into two classes:

Class I = {K : τ(K^{2}) = power of 3},
Class II = {K : τ(K^{2}) ≠ power of 3}.

But first consider the case K = 1. In this case u = v ⩽ \sqrt{x}, and the prime factors p of u satisfy p ≡ 1 (mod 3). On the other hand (u, 3) = 1. Hence, letting u = q_{1}q_{2} ⋯ q_{r}, with 5 ⩽ q_{1} < q_{2} < ⋯< q_{r}, it follows that

τ(u^{2}) = 3^{r}, φ(u^{2}) = u ∏_{j=1}^{r} (q_{j} − 1), σ(u^{2}) = ∏_{j=1}^{r} (1 + q_{j} + q_{j}^{2}).

Since (φ(u^{2}), 3) = 1 and (σ(u^{2}), 3) = 1, it follows that u^{2} ∈ R_{1}.

Hence, R_{1}(x) = #\{u ⩽ \sqrt{x} : u squarefree, (p, u) = 1 if p ≡ −1 (mod 3)\}. Since

∑_{u^{2} ∈R_{1}} \frac{1}{u^{s}} = ∏_{p≡−1 (mod 3)} ( 1 + \frac{1}{p^{s}} ) ,

one can use the classical method of Landau (see his book [9, pp. 641–649]) and deduce that

(4.5)  R_{1}(x) = c_{7} \sqrt{\frac{x}{logx}} ( 1 + O( \frac{1}{loglogx}) ) ,

for some positive constant c_{7}.

Now, assume that K ∈ class I, in which case (σ(K^{2}), 3) = 1 and (φ(K^{2}), 3) = 1. Then n = K^{2}v^{2} ⩽ x, with (K, v) = 1, belongs to R_{K} if and only if v is squarefree and all its prime factors p satisfy p ≡ −1 (mod 3), in which case

∑_{v} \frac{1}{v^{s}} = ∏_{\begin{matrix}p≡−1 (mod 3) \\ (p,K)=1 \end{matrix}} ( 1 + \frac{1}{p^{s}} ) = ∏_{p | K} ( 1 + \frac{1}{p^{s}} )^{−1} ∏_{p≡−1 (mod 3)} ( 1 + \frac{1}{p^{s}} ) .

It follows that, for K ∈ class I,

R_{K} (x) = c_{7} ∏_{p | K} ( 1 + \frac{1}{p})^{−1} \frac{1}{K} \sqrt{\frac{x}{logx}} ( 1 + O( \frac{1}{loglogx}) ) ,

implying that, for some constant c_{8} > 0,

(4.6)  ∑_{K∈class I} R_{K} (x) = c_{8} \sqrt{\frac{x}{logx}} ( 1 + O( \frac{1}{loglogx}) ) .

Consider now K ∈ class II, K ⩽ y. Let q|τ(K^{2}), q ≠ 3. In this case, q ⩽ y. If n ∈ R_{K}, then n = K^{2}v^{2} and (3, φ(v)) = 1. Consequently, p|v implies that p ≢ 1 (mod 3) and p ≢ 1 (mod q). By using the Selberg sieve, we obtain that, for some positive constant c_{9},

R_{K} (x) ⩽ c_{9} \frac{\sqrt{x}}{K} ∏_{p≡1 (mod 3) or p≡1 (mod q)} ( 1 − \frac{1}{p}) ⩽ \frac{c_{9}}{K} \begin{matrix}√ & \overline{x} \\ √ & \overline{logx} \end{matrix} ∏_{p≡−1 (mod 3) and p≡1 (mod q)} ( 1 − \frac{1}{p})

⩽ \frac{c_{9}}{K} \begin{matrix}√ & \overline{x} \\ √ & \overline{logx} \end{matrix} exp\{−\frac{1}{2(q − 1)} loglogx\} = \frac{c_{9}}{K} \begin{matrix}√ & \overline{x} \\ √ & \overline{logx} \end{matrix} · \frac{1}{(logx)^{1/(2(q−1))}} .

From this last estimate, it is clear that we can ignore those K ∈ class II. Hence the main contributions to R(x) comes from (4.5) and (4.6), thus completing the proof of Theorem 1.

5. The proof of Theorem 2

Let N := {n ∈ ℕ : l(n) = 1}. If n ∈ N, then one of the numbers τ(n) and τ(n + 1) must be odd, implying that either n or n + 1 is a square. So let us set

N_{0}(x) := #{n ⩽ x : n ∈ N , n = square},
N_{1}(x) := #{n ⩽ x : n ∈ N , n + 1 = square},

so that N(x) = N_{0}(x) + N_{1}(x). We shall therefore consider two cases, namely the case when τ(n) is odd, and thereafter the one when τ(n + 1) is odd.

We start with the first case. In this case, l(n) = 1 implies that n = u^{2}, so that τ(n + 1) = τ(u^{2} + 1). Write u = Km, where K is squarefull and m is squarefree, with (K, m) = 1. The contribution of the case m = 1 to N_{0}(x) is clearly O(x^{1/4} ), since in this case n = K^{2}m^{2} = K^{2} ⩽ x, that is K ⩽ \sqrt{x}. Similarly, write n + 1 = Rν, where R is squarefull and ν is squarefree, with (R, ν) = 1, in which case, τ(n + 1) = τ(R)2^{ω(ν)} . As above, the contribution of the case ν = 1 to N_{1}(x) is no more than O(x^{1/4} ). Hence, from here on, we will assume that m > 1 and ν > 1.

Given squarefull numbers K and R, we set

U(x|K, R) := #{n ⩽ x : n ∈ N , n = K^{2}m^{2}, m > 1, n + 1 = Rν},
V (x|K, R) := #\{1 < m ⩽ \sqrt{x}/K : K^{2}m^{2} + 1 ≡ 0 (mod R)\}.

Note that we clearly have U(x|K, R) ⩽ V (x|K, R). Hence, our first goal will be to prove

(5.1)  ∑_{max (K,R)⩾T} V (x|K, R) = o(\sqrt{x} )  (T → ∞).

Assume first that K is arbitrary and fixed. We shall sum over those positive integers m, ν for which R ⩾ K. We will find an upper bound for the number of solutions of

(5.2)  n^{2} + 1 = Rν,  R ⩾ T,  n ⩽ \sqrt{x}.

First we consider the contribution of those R in the above which have a squarefull divisor S such that T ⩽ S ⩽ \sqrt{x}. In this case, n^{2} + 1 ≡ 0 (mod R) implies that n^{2} + 1 ≡ 0 (mod S). Adding up the contributions of all such S’s, (5.2) yields at most

2 ∑_{S⩾T} \frac{\sqrt{x}}{S}ρ(S) ≪ \begin{matrix}√ & \overline{x} \\ √ & \overline{T} \end{matrix} solutions,

where we used the trivial bound ρ(S) ≪ S^{ε}.

It remains to estimate the number of solutions n ⩽ \sqrt{x} in (5.2) for which the corresponding squarefull number R ⩽ x has no squarefull divisor S ⩽ \sqrt{x}. If R has at least two prime divisors, say p and q, then p^{2}q^{2}|R and min(p^{2}, q^{2}) < \sqrt{x}, which is impossible. This means that R = p^{α} for some integer α ⩾ 2. If α ⩾ 4, then S = p^{2} < \sqrt{x}, again a contradiction. This means that we only have two possibilities, namely R = p^{2}, p^{3}. In the case R = p^{2}, we have p^{2}|n^{2} + 1, p ⩾ \sqrt{x}; thus, applying Lemma 1 with f(n) = n^{2} + 1, the assertion is proved. If R = p^{3}, the result follows even more directly.

For fixed K, there are no more than \sqrt{x}/K integers for which (Km)^{2} ⩽ x. Summing on K, we get no more than \sqrt{x} ∑ _{K⩾T} \frac{1}{K} ≪ o(\sqrt{x} ) (T → ∞), thus completing the proof of (5.1).

Now further define K_{1} := {(K, R) : (K, R) = 1 and (3τ(K^{2}), 2τ(R)) = 1}. Note that the condition (3τ(K^{2}), 2τ(R)) = 1 is a necessary condition for K^{2}m^{2} + 1 = Rν, with m > 1, to satisfy l(K^{2}m^{2}) = 1.

Now let T be a large number. Since U(x|K, R) ⩽ V (x|K, R), it follows from (5.1) that

∑_{max (K,R)⩾T} U(x|K, R) = o(\sqrt{x} ) (T → ∞).

In particular, we have

U(x|1, 1) = ∑_{m⩽\sqrt{x}} |μ(m^{2} + 1)| · |μ(m)|,

so that by Lemma 2, U(x|1, 1) = ξ_{2}(1 + o(1))\sqrt{x}.

Now we have

(5.3)  N_{0}(x) = ∑_{K,R∈K_{1}} U(x|K, R),

where

(5.4)  U(x|K, R) = ∑_{\begin{matrix}(δ_{1} ,K)=1 \\ (δ_{2} ,R)=1 \end{matrix}} μ(δ_{1})μ(δ_{2})Q(K, R; δ_{1}, δ_{2}),

with

Q(K, R; δ_{1}, δ_{2}) = #{K^{2}δ_{1}^{4}m_{1}^{2} + 1 = Rδ_{2}^{2}ν_{1} ⩽ x, (ν_{1}, R) = 1, (m_{1}, K) = 1}

= ∑_{d_{1} |R} μ(d_{1}) ∑_{d_{2} |K} μ(d_{2}) · #{K^{2}δ_{1}^{4}d_{2}^{2}m_{2}^{2} + 1 = Rδ_{2}^{2}d_{1}ν_{2} ⩽ x}, (5.5)

where this last expression was obtained by setting ν_{1} = d_{1}ν_{2} and m_{1} = d_{2}m_{2}. Now let E_{0} = Kδ_{1}^{2}d_{2} and F_{0} = Rδ_{2}^{2}d_{1}, so that

#{K^{2}δ_{1}^{4}d_{2}^{2}m_{2}^{2} + 1 = Rδ_{2}^{2}d_{1}ν_{2} ⩽ x} = V (x|E_{0}, F_{0}).

Since R, K ⩽ T, it follows that d_{1}, d_{2} ⩽ T. But as we have seen earlier, the contribution of those V (x|E_{0}, F_{0}) for which max(δ_{1}, δ_{2}) ⩾ T, is small.

In light of this observation and using (5.5), relation (5.4) can be replaced by

(5.6) U(x|K, R) = ∑_{\begin{matrix}(δ_{1} ,K)=1 \\ (δ_{2} ,R)=1 \\ δ_{1} ⩽T, δ_{2} ⩽T \end{matrix}} μ(δ_{1})μ(δ_{2})Q(K, R; δ_{1}, δ_{2}) + o(\sqrt{x} )  (T → ∞).

If E_{0} and F_{0} are bounded,

V (X|E_{0}, F_{0}) = \frac{\sqrt{x}}{E_{0}F_{0}} ρ(F_{0}) + O(ρ(F_{0})).

Consequently, (5.6) becomes

U(x|K, R) = ∑_{{(δ_{1} ,K)=1 \atop δ_{1} ⩽T}}  ∑_{{(δ_{2} ,R)=1 \atop δ_{2} ⩽T}}  ∑_{d_{1} |R} μ(d_{1}) ∑_{d_{2} |K} μ(d_{2}) ( \frac{\sqrt{x}ρ(Rδ_{2}^{2}d_{1})}{Kδ_{1}^{2}d_{2}Rδ_{2}^{2}d_{1}} + O(ρ(Rδ_{2}^{2}d_{1})))

+o(\sqrt{x}) (T → ∞). (5.7)

Setting

(5.8) C(K, R) := \frac{1}{KR} ∑_{(δ_{1} ,K)=1} ∑_{(δ_{2} ,R)=1} ∑_{d_{1} |R} ∑_{d_{2} |K} \frac{μ(δ_{1})μ(δ_{2})μ(d_{1})μ(d_{2})ρ(Rδ_{2}^{2}d_{1})}{δ_{1}^{2}δ_{2}^{2}d_{1}d_{2}}

and noticing that the right hand side of (5.8) represents a finite quantity, we may conclude that C(K, R) is a nonnegative (actually positive) constant. Hence, in light of this last observation, (5.7) and (5.8) yield

(5.9)  U(x|K, R) = C(K, R)(1 + o(1))\sqrt{x}.

Since ∑ _{(K,R)∈K_{1}} C(K, R) is convergent, it follows, combining (5.3) and (5.9), that

N_{0}(x) = ∑_{K,R∈K_{1}} U(x|K, R) = (1 + o(1))c_{10} \sqrt{x} (x → ∞),

where c_{10} = ∑ _{(K,R)∈K_{1}} C(K, R) is a constant which is positive because C(1, 1) is positive by Lemma 2.

It remains to consider the second case, namely the one where τ(n+1) is odd, in which case n+1 is a square. In this case, l(n) = 1 implies that n+1 = K^{2}m^{2}, where K is squarefull, m > 1 squarefree, (K, m) = 1, n = Rν, (ν, R) = 1, R squarefull and ν squarefree. Now, l(n) = 1 also implies that (2τ(R), 3τ(K^{2})) = 1. Hence, let K_{2} stand for the set of all pairs of squarefull integers K, R, with (K, R) = 1, for which

(5.10)  (2τ(R), 3τ(K^{2})) = 1.

Observe that K = R = 1 satisfies (5.10) and that we have

N_{1}(x) = ∑_{K,R∈K_{2}} #{Rν ⩽ x : K^{2}m^{2} − 1 = Rν, m > 1,
(K, m) = (R, ν) = 1, μ^{2}(m) = μ^{2}(ν) = 1}.

Proceeding along the same lines as in the first case yields the estimate

N_{1}(x) = (1 + o(1))c_{11} \sqrt{x} (x → ∞),

for some positive constant c_{11}. Since the rest of the proof is similar, we shall omit it. This completes the proof of Theorem 2.

References

[1] K. Alladi, On the probability that n and Ω(n) are relatively prime, Fib. Quart. 19 (1981), 228-233.

[2] J. M. De Koninck and I. Kátai, On an estimate of Kanold, Int. J. Math. Anal. 5/8 (2007), no. 1–12, 9–18.

[3] P. D. T. A. Elliott, Probabilistic Number Theory I, Mean Value Theorems, Springer-Verlag, Berlin, 1979.

[4] P. Erdős, Some asymptotic formulas in number theory, J. Indian Math. Soc. (N. S.) 12 (1948), 75–78.

[5] C. Hooley, Applications of Sieve Methods to the Theory of Numbers, Cambridge Tracts in Mathemtics,

[6] A. Ivić, The Riemann Zeta-Function, Dover, New York, 1985.

[7] H. J. Kanold, Über das harmonische Mittel der Teiler einer natürlichen Zahl II, Math. Annalen 134 (1958), 225–231.

[8] I. Kátai, On an application of the large sieve: shifted prime numbers, which have no prime divisors from a given arithmetical progression, Acta Math. Acad. Sci. Hung. 21(1–2) (1970), 151–173.

[9] E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd II, Teubner, Leipzig, 1909.

Dép. de mathématiques et de statistique (Received 09 11 2009) Université Laval (Revised 26 02 2010) Québec Québec G1V 0A6 Canada

jmdk@mat.ulaval.ca

Computer Algebra Department Eötvös Loránd University 1117 Budapest Pázmány Péter Sétány I/C Hungary

katai@compalg.inf.elte.hu