A Gcd-Sum Function Over Regular Integers Modulo n

László Tóth Institute of Mathematics and Informatics University of Pécs Ifjúság u. 6 7624 Pécs Hungary

                       ltoth@ttk.pte.hu

Abstract We introduce a gcd-sum function involving regular integers (mod n) and prove

results giving its minimal order, maximal order and average order.

1 Introduction

Let n > 1 be an integer with prime factorization n = p_{1}^{ν_{1}} ⋯ p_{r}^{ν_{r}}. An integer k is called regular (mod n) if there exists an integer x such that k^{2}x ≡ k (mod n), i.e., the residue class of k is a regular element (in the sense of J. von Neumann) of the ring ℤ_{n} of residue classes (mod n). In general, an element k of a ring R is said to be (von Neumann) regular if there is an x ∈ R such that k = kxk. If every k ∈ R has this property, then R is called a von Neumann regular ring, cf. for example [9, p. 110].

It can be shown that k ≥ 1 is regular (mod n) if and only if for every i ∈ {1, …, r} either p_{i} ∤ k or p_{i}^{ν_{i}} | k. Also, k ≥ 1 is regular (mod n) if and only if gcd(k, n) is a unitary divisor of n. We recall that d is said to be a unitary divisor of n if d | n and gcd(d, n/d) = 1, and use the notation d || n. These and other characterizations of regular integers are given in our paper [15].

Let Reg_{n} = {k : 1 ≤ k ≤ n and k is regular (mod n)}, and let ϱ(n) = # Reg_{n} denote the number of regular integers k (mod n) such that 1 ≤ k ≤ n. The function ϱ(n) was investigated in paper [15]. It is multiplicative and ϱ(p^{ν}) = ϕ(p^{ν}) + 1 = p^{ν} − p^{ν−1} + 1 for every prime power p^{ν} (ν ≥ 1), where ϕ is the Euler function. Note that (ϱ(n) : n ∈ ℕ) is the sequence \underline{A055653} in Sloane’s On-Line Encyclopedia of Integer Sequences.

In this paper we introduce the function

P̃(n) := ∑_{k∈Reg_{n}} gcd(k, n).  (1)

This is analogous to the gcd-sum function, called also Pillai’s arithmetical function,

P (n) := ∑_{k=1}^{n} gcd(k, n),  (2)

investigated in the recent papers [1, 2, 3, 4, 13] of this journal. This is sequence \underline{A018804} in Sloane’s Encyclopedia.

Note that the function P (n) was introduced by S. S. Pillai [11], showing that

P (n) = ∑_{d|n} dϕ(n/d), ∑_{d|n} P (d) = nτ(n) = ∑_{d|n} σ(d)ϕ(n/d),

where τ(n) and σ(n) denote, as usual, the number and the sum of divisors of n, respectively. Note also, that for any arithmetical function f,

P_{f}(n) := ∑_{k=1}^{n} f(gcd(k, n)) = ∑_{d|n} f(d)ϕ(n/d),  (3)

which is a result of E. Cesàro [5]. See also the book [7, p. 127].

O. Bordellès [1] showed that

P = μ ∗ (E · τ),  (4)

where ∗ denotes the Dirichlet convolution, where E(n) = n and μ is the Möbius function. Then, using this representation he proved the following asymptotic formula: for every ε > 0,

∑_{n≤x} P (n) = \frac{x^{2}}{2ζ(2)} (log x + 2γ − \frac{1}{2} − \frac{ζ′(2)}{ζ(2)}) + O(x^{1+θ+ε}),  (5)

where γ is Euler’s constant and θ is the number appearing in Dirichlet’s divisor problem, that is

∑_{n≤x} τ(n) = x log x + (2γ − 1)x + O(x^{θ+ε}).  (6)

It is known that 1/4 ≤ θ ≤ 131/416 ≈ 0.3149.

Formulae (4) and (5) were obtained, even in a more general form, in the paper [6], where the authors proved also the following result concerning the maximal order of P (n),

lim sup_{n→∞} \frac{log(P (n)/n) log log n}{log n} = log 2,  (7)

which is well known for the function τ(n) instead of P (n)/n.

Asymptotic formulae for generalized gcd-sum functions of type (3), concerning sets of polynomials with integral coefficients and regular convolutions were given in our paper [14].

We investigate in what follows arithmetical and asymptotical properties of the function P̃(n). We show that it is multiplicative and for every n ≥ 1,

P̃(n) = n ∏_{p|n} (2 − \frac{1}{p}) .  (8)

Further, we show that the result (7) holds also for the function P̃(n), its minimal order is 3n/2 and prove an asymptotic formula for its summatory function both without assuming the Riemann hypothesis and assuming the Riemann hypothesis (RH), based on a convolution identity analogous to (4).

Our results and proofs involve properties of arithmetical functions defined by unitary divisors and of the unitary convolution. For background material in this topic we refer to the book [10].

As an open question we formulate the following: What is the minimal order of the Pillai function P (n)?

A common generalization of the functions P (n) and P̃(n) is outlined at the end of Section 2.

2 Arithmetical properties

Let f be an arbitrary arithmetical function and consider the more general function

P̃_{f}(n) := ∑_{k∈Reg_{n}} f(gcd(k, n)).

Proposition 1. For every n ≥ 1,

P̃_{f}(n) = ∑_{d||n} f(d) ϕ(n/d).  (9)

Proof. The integer k ≥ 1 is regular iff gcd(k, n) || n, cf. the Introduction, and obtain

P̃_{f}(n) = ∑_{k=1}^{n} ∑_{d||n} f(d) = ∑_{d||n} f(d) ∑_{\begin{matrix}1≤j≤n/d \\ (j,n/d)=1 \end{matrix}} 1 = ∑_{d||n} f(d)ϕ(n/d).

Corollary 1. If f is multiplicative, then P̃_{f} is also multiplicative and P̃_{f}(p^{ν}) = f(p^{ν}) + p^{ν} − p^{ν−1} for every prime power p^{ν} (ν ≥ 1).

In particular, P̃ is multiplicative and P̃(p^{ν}) = 2p^{ν} − p^{ν−1} for every prime power p^{ν} (ν ≥ 1).

Proof. According to (9), P̃_{f} is the unitary convolution of the functions f and ϕ. It is known that the unitary convolution preserves the multiplicativity of functions. In particular, for f(n) = n we obtain that P̃ is multiplicative and the explicit formula (8).

Let ω(n, k) denote the number of distinct prime factors of n which do not divide k. For k = 1, ω(n) := ω(n, 1) is the number distinct factors of n. Also, let τ^{∗}(n, k) denote the number of unitary divisors of n which are relatively prime to k. Here τ^{∗}(n) := τ^{∗}(n, 1) is the number of unitary divisors of n. We have τ^{∗}(n, k) = 2^{ω(n,k)} and τ^{∗}(n) = 2^{ω(n)}.

Another representation of P̃ is given by

Proposition 2. For every n ≥ 1,

P̃(n) = ∑_{de=n} μ(d)e · 2^{ω(e,d)}.

Proof. By Proposition 1,

P̃(n) = ∑_{\begin{matrix}de=n \\ (d,e)=1 \end{matrix}} dϕ(e) = ∑_{\begin{matrix}de=n \\ (d,e)=1 \end{matrix}} d ∑_{ab=e} μ(a)b = ∑_{\begin{matrix}dab=n \\ (d,a)=1 \\ (d,b)=1 \end{matrix}} dμ(a)b

= ∑_{ac=n} μ(a)c ∑_{\begin{matrix}bd=c \\ (b,d)=1 \\ (d,a)=1 \end{matrix}} 1 = ∑_{ac=n} μ(a)c τ^{∗}(c, a).

Proposition 3. For every n ≥ 1 we have P̃(n) ≤ P (n), with equality iff n is square-free, and 2^{ω(n)}ϕ(n) ≤ P̃(n) ≤ 2^{ω(n)}n, with equality iff n = 1.

Proof. This follows at once by (1), (2) and (8).

Remark 1. Let P̂(n) := ∑_{k∈Reg_{n}} lcm[k, n]. Then it follows, similar to the “usual” lcm-sum

function that for every n ≥ 1,

P̂(n) = \frac{n}{2} (1 + ∑_{d||n} dϕ(d)) .

Remark 2. For every n ∈ ℕ let A(n) be an arbitrary nonempty subset of the set of positive divisors of n. For the system of divisors A = (A(n) : n ∈ ℕ) and for an arbitrary arithmetical function f consider the following restricted summation of the gcd’s:

P_{A,f}(n) = ∑_{\begin{matrix}1≤k≤n \\ gcd(k,n)∈A(n) \end{matrix}} f(gcd(k, n)).

It follows, similar to the proof of Proposition 1, that

P_{A,f}(n) = ∑_{d∈A(n)} f(d)ϕ(n/d).

If A(n) is the set of all (positive) divisors of n, then we have the function (3) and if A(n) is the set of the unitary divisors of n, then we reobtain (9).

If A is a regular system of divisors of Narkiewicz-type, including the previous two special cases, then P_{A,f} is the A-convolution of the functions f and ϕ. It turns out, that P_{A,f} is multiplicative provided f is multiplicative, cf. [10, Ch. 4].

Other special cases for A can also be considered, for ex. A(n) the set of prime divisors of n or A(n) the set of exponential divisors of n.

3 Asymptotic properties

Theorem 1. The minimal order of P̃(n) is 3n/2 and the maximal order of log(P̃(n)/n) is log 2 log n/ log log n.

Proof. From (8) we have P̃(n) ≥ n(3/2)^{ω(n)} ≥ 3n/2 for every n ≥ 1, with equality for n = 2^{ν} (ν ≥ 1), giving the minimal order of P̃(n).

For the maximal order take into account (7), where the limsup is attained for a sequence of square-free integers (more exactly for n_{k} = ∏_{k/ log^{2} k<p≤k} p, k → ∞), see [6, Theorem 4.1], and use P̃(n) ≤ P (n) for every n ≥ 1, with equality iff n is square-free, by Proposition 3.

In what follows we prove the following asymptotic formula for the function P̃. Let ψ(n) = n ∏_{p|n}(1 + 1/p) denote the Dedekind function,

α(n) := ∑_{p|n} \frac{log p}{p − 1}, β(n) = ∑_{p|n} \frac{log p}{p^{2} − 1},

δ(x) := exp (−A(log x)^{3/5}(log log x)^{−1/5}) ,

η(x) := exp (B log x(log log x)^{−1}) ,

where A and B are positive constants and let θ be the exponent in (6).

Theorem 2. We have

∑_{n≤x} P̃(n) = \frac{x^{2}}{2ζ(2)}(K_{1} log x + K_{2}) + O(x^{3/2}δ(x)),  (10)

where the constants K_{1} and K_{2} are given by

K_{1} := ∑_{n=1}^{∞} \frac{μ(n)}{nψ(n)} = ∏_{p} (1 − \frac{1}{p(p + 1)}) ,

K_{2} := K_{1} (2γ − \frac{1}{2} − \frac{2ζ′(2)}{ζ(2)}) − ∑_{n=1}^{∞} \frac{μ(n)(log n − α(n) + 2β(n))}{nψ(n)}.

If RH is true, then the error term of (10) is O(x^{(7−5θ)/(5−4θ)}η(x)).

Remark 3. Here K_{1} ≈ 0.7042. Note that K_{1} = lim_{x→∞} \frac{2}{x^{2}} ∑_{n≤x} γ(n), where γ(n) = ∏_{p|n} p is the

greatest square-free divisor of n. Also, K_{1}/ζ(2) ≈ 0.4282 is the so called “carefree constant”, cf. [8, Section 2.5.1]. For θ ≈ 0.3149 one has (7 − 5θ)/(5 − 4θ) ≈ 1.4505.

Proof. We need the following auxiliary results. Let σ′_{s}(n) be the sum of s-th powers of the square-free divisors of n.

Lemma 1. ([12, Theorems 4.3, 5.2]) If k ≥ 1 is an integer, then for every ε > 0,

∑_{n≤x} 2^{ω(n,k)} = \frac{kx}{ζ(2)ψ(k)} (log x + α(k) − 2β(k) + 2γ − 1 − \frac{2ζ′(2)}{ζ(2)})

+O (σ′_{−1+ε}(k)σ′_{−θ}(k)x^{1/2}δ(x)) ,  (11)

the O estimate being uniform in x and k.

If RH is true, then x^{1/2}δ(x) in the error term of (11) can be replaced by x^{(2−θ)/(5−4θ)}η(x).

Note that

α(n) = O(log n), β(n) = O(1),  (12)

since α(n) ≤ ∑_{p|n} log p = log γ(n) ≤ log n and β(n) ≪ ∑_{p|n} \frac{log p}{p^{2}} ≤ ∑_{p} \frac{log p}{p^{2}} < ∞.

Lemma 2. For every ε > 0,

∑_{n≤x} 2^{ω(n,k)}n = \frac{kx^{2}}{2ζ(2)ψ(k)} (log x + α(k) − 2β(k) + 2γ − \frac{1}{2} − \frac{2ζ′(2)}{ζ(2)})

+O (σ′_{−1+ε}(k)σ′_{−θ}(k)x^{3/2}δ(x)) ,  (13)

If RH is true, then x^{3/2}δ(x) in the error term of (13) can be replaced by x^{(7−5θ)/(5−4θ)}η(x).

Proof. By partial summation from Lemma 1.

We can now complete the proof of Theorem 2. By Proposition 2 and Lemma 2,

∑_{n≤x} P̃(n) = ∑_{d≤x} μ(d) ∑_{e≤x/d} 2^{ω(e,d)}e

= \frac{x^{2}}{2ζ(2)} (∑_{d≤x} \frac{μ(d)}{dψ(d)} (log x + 2γ − \frac{1}{2} − \frac{2ζ′(2)}{ζ(2)}) − ∑_{d≤x} \frac{μ(d)(log d − α(d) + 2β(d))}{dψ(d)})

+O (∑_{d≤x} σ′_{−1+ε}(d)σ′_{−θ}(d)(x/d)^{3/2}δ(x/d)) .

For every ε > 0 and x sufficiently large, x^{ε}δ(x) is increasing, therefore

(x/d)^{3/2}δ(x/d) = (x/d)^{3/2−ε}(x/d)^{ε}δ(x/d) ≤ (x/d)^{3/2−ε}x^{ε}δ(x) = x^{3/2}δ(x)/d^{3/2−ε}.

Furthermore, it is enough to use the inequalities σ′_{−1+ε}(d) ≤ τ(d) (for ε < 1) and σ′_{−θ}(d) ≤ τ(d) and then obtain the given formula using (12) and the well known estimates

∑_{d>x} \frac{1}{d^{2}} ≪ \frac{1}{x}, ∑_{d>x} \frac{log d}{d^{2}} ≪ \frac{log x}{x}.

If we assume RH and in the error term use the property that η(x) is increasing, so η(x/d) ≤ η(x) for d ≥ 1.

4 Acknowledgement

The author thanks the referee for helpful suggestions.

References

[1] O. Bordellès, A note on the average order of the gcd-sum function, J. Integer Sequences 10 (2007), Article 07.3.3.

[2] O. Bordellès, Mean values of generalized gcd-sum and lcm-sum functions, J. Integer Sequences 10 (2007), Article 07.9.2.

[3] K. Broughan, The gcd-sum function, J. Integer Sequences 4 (2001), Article 01.2.2.

[4] K. Broughan, The average order of the Dirichlet series of the gcd-sum function, J. Integer Sequences 10 (2007), Article 07.4.2.

[5] E. Cesàro, Étude moyenne du plus grand commun diviseur de deux nombres, Ann. Mat. Pura. Appl. (1) 13 (1885), 235–250.

[6] J. Chidambaraswamy, R. Sitaramachandrarao, Asymptotic results for a class of arithmetical functions, Monatsh. Math. 99 (1985), 19–27.

[7] L. E. Dickson, History of the Theory of Numbers, vol. I, Chelsea, New York, 1971.

[8] S. R. Finch, Mathematical Constants, Cambridge University Press, 2003.

[9] I. Kaplansky, Fields and Rings, University of Chicago Press, 1972.

[10] P. J. McCarthy, Introduction to Arithmetical Functions, Springer, 1986.

[11] S. S. Pillai, On an arithmetic function, J. Annamalai Univ. 2 (1933), 243–248.

[12] D. Suryanarayana, V. Siva Rama Prasad, The number of k-free and k-ary divisors of m which are prime to n. J. Reine Angew. Math. 264 (1973), 56–75.

[13] Y. Tanigawa, W. Zhai, On the gcd-sum function, J. Integer Sequences 11 (2008), Article 08.2.3.

[14] L. Tóth, A generalization of Pillai’s arithmetical function involving regular convolutions, Acta Math. Inform. Univ. Ostraviensis 6 (1998), 203–217, available at

    http://www.ttk.pte.hu/matek/ltoth/TothGeneralizationPillai(1998).pdf

[15] L. Tóth, Regular integers (mod n), Annales Univ. Sci. Budapest., Sect. Comp. 29

    (2008), 263–275, available at http://front.math.ucdavis.edu/0710.1936

2000 Mathematics Subject Classification: Primary 11A25; Secondary 11N37. Keywords: regular integers (mod n), gcd-sum function, unitary divisor, Dirichlet divisor problem, Riemann hypothesis.

(Concerned with sequences \underline{A055653}, \underline{A018804}.)

Received October 6 2008; revised version received January 21 2009. Published in Journal of Integer Sequences, February 13 2009.

Return to Journal of Integer Sequences home page.