# Arithmetical Functions Associated with thek-ary Divisors of an Integer

Authors: Joseph Vade Burnett; Sam Grayson; Zachary Sullivan; Richard Van Natta; Luke Bang
Journal: International Journal of Mathematics and Mathematical Sciences
 (2018)

---

## Abstract

Thek-ary divisibility relations are a class of recursively defined relations beginning with standard divisibility and culminating in the so-called infinitary divisibility relation. We examine the summatory functions corresponding to the k-ary analogues of various popular functions in number theory, proving various results about the structure of the k-ary divisibility relations along the way.


---

## Body

## 1. Introduction

Letn be a positive integer and denote the set of divisors of n by D(n). The set of unitary divisors of n, denoted by D1(n), are the divisors d of n which satisfy Dd∩Dn/d={1}; in other words, (d,n/d)=1. The biunitary divisors of n are the divisors d of n which satisfy D1(d)∩D1(n/d). This differs from some definitions of biunitary divisibility in the literature (e.g., [1]) but is consistent with others (e.g., [2]). In general, we may define the k-ary divisors of an integer n to be the set (1)Dkn≔d∈Dn∣Dk-1d∩Dk-1nd=1=d∈Dn∣d,ndk-1=1,where we define the greatest common k-ary divisor of m and n by (2)m,nk≔max⁡Dkm∩Dkn.We write dkn if d∈Dk(n).Thek-ary divisibility relations as defined above were first introduced by Cohen [3] and have been studied more recently by Haukkanen [2] and Steuding et al. [4]. An alternative definition can be seen in Suryanarayana [5].One easily verifies the following basic properties:(i)
1∈Dk(n) and n∈Dk(n) for all n.(ii)
Ifn and m are coprime, then Dk(nm)=Dk(n)·Dk(m), where A·B≔{ab∣a∈A,b∈B}.(iii)
Ifd∈Dk(n), then n/d∈Dk(n).For example, the set of unitary divisors of a prime powerpa are D1(pa)={1,pa}. On the other hand, the biunitary divisors of a prime power pa are given by D(pa) when a is odd and D(pa)∖{pa/2} when a is even. We may then form the unitary and biunitary divisors of a positive integer n by “multiplying” the prime-power divisor sets that form the prime decomposition of n.By viewing the setsDk as representing some of the A-convolutions of Narkiewicz [6], we may define the k-ary convolution of arithmetic functions f and g: (3)f⋆kgn≔∑dknfdgnd.The following properties ofk-ary convolution can be found in [2]:(i)
Thek-ary convolution is commutative.(ii)
The functionι(n), which takes on value of 1 if n=1 and 0 otherwise, is the identity under k-ary convolution.(iii)
If an arithmetic functionf satisfies f(1)≠0, then f possesses a unique inverse under k-ary convolution.(iv)
Iff and g are multiplicative functions, then f⋆kg is multiplicative as well.By choosingf and g appropriately, we may obtain multiplicative k-ary analogues to the following classical functions from number theory in terms of the k-ary convolution:(i)
Letf(n)=g(n)=1 for all n. Then τk(n)≔(f⋆kg)(n) is the number of k-ary divisors of n.(ii)
Letf(n)=n and g(n)=1 for all n. Then σk(n)≔(f⋆kg)(n) is the sum of the k-ary divisors of n.(iii)
Letf(n)=n and g(n)=μk(n) for all n, where μk is the unique inverse of the function U(n)=1 under the k-ary convolution. Then φk(n)≔(f⋆kg)(n) is the analogue of the Euler totient function.(iv)
Letf(n)=n and g(n)=μkn. Then ψk(n)≔(f⋆kg)(n) is the analogue of the Dedekind ψ-function.Note that whileφ(n) counts the totatives of n, in general φk does not count the k-ary totatives of n.In this paper, we prove results concerning the structure ofk-ary divisibility relations and use that to obtain formulae for the number of integers m less than or equal to n which satisfy (m,n)k=1. We then apply this result to obtain asymptotics for the summatory functions of k-ary generalizations of the classical functions mentioned above.


## 2. The Behavior ofk-Ary Divisibility Relations

LetD∞(n) be the set of infinitary divisors of n introduced and studied by Cohen [3, 7]. The infinitary divisibility relation can be thought of as the end behavior of the recursion defining the k-ary divisibility relations. It satisfies(i)
All properties ofk-ary divisibility relations listed above(ii)
d∈D∞(n) if and only if D∞(d)∩D∞(n/d)=1(iii)
D∞ being transitive; that is, for all n, if d∈D∞(n), then D∞(d)⊆D∞(n).Additionally, the following reformulation of Theorem 1 from [3] characterizes in what sense k-ary divisibility relations “approach” the infinitary divisibility relation as k increases.Theorem 1.
Letk⩾0 be given, and suppose that n∈N is such that, for every prime p, νp(n)⩽k+1, where νp(n) is the exponent of the prime p in the prime decomposition of n (0 if p does not divide n). Then Dk(n)=D∞(n).Proof.
We proceed by induction onk. We need to only show the result for prime powers pa, since by the second property listed above we obtain our theorem by multiplicative construction, akin to the treatment of multiplicative arithmetical functions. Therefore, we may speak of a set prime p and consider pa, with a⩽k+1. For k=0, we have D∞(p)=D(p) and D∞(1)=D(1).
Now assume that the result holds up to someK-1. Then consider DK(pa)={d∈D(pa)∣DK-1(d)∩DK-1(pa/d)=1}, with a such that a⩽K+1. Notice that all divisors d of pa, except pa itself, satisfy d=pb, with b⩽K-1. Then, for d≠pa, we have DK-1(d)=D∞(d) and, for d≠1, we have DK-1(pa/d)=D∞(pa/d). So, for d not equal to 1 or pa, d∈DK(pa)⟺D∞(d)∩D∞(pa/d). But 1 and pa are in DK(pa) as well, so DK(pa)=D∞(pa), and by the second property of Dk and D∞ listed above, we are done.Additionally, we observe the following.Theorem 2.
For alln∈N, k⩾0, D∞(n)⊆D2k+2(n)⊆D2k(n), and D2k+1(n)⊆D2k+3(n)⊆D∞(n).Proof.
We will again use induction. One can immediately verify thatD∞(n)⊆D2(n)⊆D(n) and D1(n)⊆D3(n)⊆D∞(n); D3(pa) only differs from D1(pa) at a=3 and a=6, where we have D3(p3)=D∞(p3) and D3(p6)=D∞(p6). Assuming that the theorem holds up to some K, observe that for each divisor d of n the condition D2K+3(d)∩D2K+3(n/d)=1 implies that D2K+1(d)∩D2K+1(n/d)=1} on account of D2K+1(d)⊆D2K+3(d) for each d. Then D2K+4(n)⊆D2K+2(n). But then, by the same reasoning, D2K+3(n)⊆D2K+5(n).
To see thatD∞(n) is ordered according to the theorem, consider the statement D∞(n)⊆D(n) for all n. Using the argument from above and the fact that D∞(n)={d∈D(n)∣D∞(d)∩D∞(n/d)=1}, we conclude that, for all k, D2k+1(n)⊆D∞(n)⊆D2k(n) and hence our relations hold.We observe that when looking at thek-ary divisors of the powers of a specific prime number, there is always an integer after which, for each a, the k-ary divisors of pa will be either D2(pa) or D1(pa).Theorem 3.
Letk>2 be given. Then there is an integer Nk such that, for all a>Nk and all primes p, Dk(pa)=D1(pa) if k is odd, and Dk(pa)=D2(pa) if k is even.Proof.
We note first that, fork=1 and k=2, we have that N1=1 and N2=3 trivially suffice for bounds. Now assume that such an Nk exists for all k=M-1. We consider the cases even M and odd M, respectively.
For evenM, take a>2NM-1 and let b⩽a/2. Then Dk(pa-b)∩Dk(pb)={1}, since Dk(pa-b)=D1(pa-b) and b<a-b. For 2b=a, we have pb∉DM(pa) as desired. Since k-ary divisions are symmetric, this argument holds for b′=a-b as well. We see then that we may take NM=2NM-1 for even M.
For oddM, take a>3NM-1. Let b be such that 0⩽b⩽(2/3)a. Then DM-1(pa-b)∩DM-1(pb)={1} if pb∈DM-1(pa-b). This occurs for all b and a satisfying a≠3b. If a=3b, then b>NM-1, so Dk(pb)=D2(pb). In either case, DM-1(pa-b)∩DM-1(pb)={1}, so that DM-1(pa)=D1(pa). We then see that we may take NM>3NM-1 for odd M.Definition 4.
We denote byNk⋆ the least Nk for a given k.Our next section concerns itself withk-ary analogues of some classical results on summatory functions.


## 3. Summatory Functions

Letk>0 be given and let f(n) be an arithmetical function constructed as follows: (4)fn≔∑d∈Dkngdndr,where r is a positive integer and g(n) is a function such that g(n)=O(nr-1). We wish to explore the end behavior of the summatory function of f: (5)Sfx≔∑n⩽xfnWe will employ techniques already used in [7, 8] to derive the result for the infinitary and unitary cases, respectively.Definition 5.
Letk⩾0 and r>0. We introduce the following function: (6)φk,rx,n≔∑m⩽xm,nk=1mr.Forr=0, this function counts the number of integers m that are less than x and k-ary coprime to n. It is known that, for k=0, φ0,0(x,n)=x(φ(n)/n)+O(τ(n)). The summatory functions for φk,0 may be broken into the case of even k or odd k, in accordance with whether Dk(n)⊆D∞(n) or D∞(n)⊆Dk(n).Theorem 6.
Letk>0 be an integer. Then, for even k, φk,0(x,n)=x(φ(n)/n)Kk(n)+O(τ~k(n)τ(n)), with (7)Kkn=∏p∣n∑b=0pb,pνpnk=1∞1pband (8)τ~kn=∏p∣n∑b=0pb,pνpnk=1∞1;for odd k, (9)φk,0x,n=x1-∑d∈D1nφdμ1ddKkd+Oτ~knτ1nτn,with the following:(i)
τ1(n) is the number of elements (divisors) in D1(n).(ii)
μ1(n) is the Möbius function corresponding to D1: μ1(n)=(-1)ω(n), where ω(n) is the number of distinct prime factors of n, counted without multiplicity.(iii)
(10)Kkn=∏p∣n∑b=0pb,pνpnk>11pb.(iv)
(11)τ~kn=∏p∣n∑b=0pb,pνpnk>11.Proof.
First note thatKk(n) and τ~k(n) are well defined: by Theorem 3, for even k, the number of integers m satisfying the condition (m,n)k=1 for a given integer n must be finite, whereas for odd k and for each maximal prime power dividing n, the number of integers satisfying (pb,pνp(n))k>1 must be finite, and hence the product over sums of prime powers k-ary-coprime to n must be finite. Therefore, the sums are finite. We will prove the result for even k first.
Letk be even and consider (12)φk,0x,n=∑m⩽xm,nk=11=∑m⩽xm=m1m2m1,n=1m2,nk=1corem2∣n1,where(13)corem2≔∏p∣m2pis the square-free part of the integer m2, from [8]. Here we have split each m uniquely into a part that has no common divisor with n and a part whose prime decomposition uses only the primes of n (note that there is no restriction on the prime powers used; e.g., m2=n2 may appear in this decomposition for large enough x).
We proceed:(14)∑m⩽xm=m1m2m1,n=1m2,nk=1corem2∣n1=∑m2:corem2∣nm2,nk=1∑m1⩽x/m2m1,n=11=∑m2:corem2∣nm2,nk=1φ0,0xm2,n=∑m2:corem2∣nm2,nk=1xφnnm2+Oτn,using the fact that the behavior of φ0,0(x,n) is known. Pulling out the constants with respect to the sum then immediately gives us our result.
For oddk, we proceed in a different manner: (15)∑m⩽xm,nk=1=x-∑m⩽xm,nk>11.We then analyze the term (16)∑m⩽xm,nk>11:
We wish to splitm into m1m2 as before. However, this should be done in such a way as to be both unique and useful in dealing with the requirement that (m,n)k>1. For each divisor d of n, let m=m1m2, with corem2∣d∣n, (m1,n)=1, and (m2,pνp(d))k>1 for each p∣d. We invoke the principle of inclusion-exclusion, enabling us to write (17)∑m⩽xm,nk>1=∑m⩽xm=m1m2m1,p1νp1n=1corem2∣p1νp1nm2,p1νp1nk>11+∑m⩽xm=m1m2m1,p2νp2n=1corem2∣p2νp2nm2,p2νp2nk>11+⋯+∑m⩽xm=m1m2m1,psνpsn=1corem2∣psνpsnm2,psνpsnk>11-∑m⩽xm=m1m2m1,p1νp1np2νp2n=1corem2∣p1νp1np2νp2nm2,p1νp1nk>1m2,p2νp2nk>11+∑m⩽xm=m1m2m1,p1νp1np3νp3n=1corem2∣p1νp1np3νp3nm2,p1νp1nk>1m2,p3νp3nk>11+⋯+∑m⩽xm=m1m2m1,ps-1νps-1npsνpsn=1corem2∣ps-1νps-1npsνpsnm2,ps-1νps-1nk>1m2,psνpsnk>11+⋯+-1s∑m⩽xm=m1m2m1,n=1corem2∣nm2,p1νp1nk>1m2,p2νp2nk>1⋮m2,psνpsnk>11,
where(18)n=∏l=1splνpln,with pl being an appropriately indexed set of primes, and we use the fact that, for d = 1, the sum is 0.
This simplifies to(19)-∑d∈D1nμ1d∑m2:corem2∣d∀p∣d,m2,pνpdk>1∑m1⩽x/m2m1,d=11=-∑d∈D1nμ1d∑m2:corem2∣d∀p∣d,m2,pνpdk>1φ0,0xm2,d==-∑d∈D1nμ1d∑m2:corem2∣d∀p∣d,m2,pνpdk>1xφddm2+Oτd==-x∑d∈D1nμ1dφdd∑m2:corem2∣d∀p∣d,m2,pνpdk>11m2+O∑d∈D1nμ1dτdφdd∑m2:corem2∣d∀p∣d,m2,pνpdk>11==-∑d∈D1nφdμ1ddKkd+Oτ~knτ1nτn,and our result follows.We letLk(n) be the coefficient appearing in front of the “x” term in φk,0(x,n) and let Ek(n) be the function in the error term, so that φk,0(x,n)=xLk(n)+O(E(n)).Remark 7.
Regarding the functionτ~k(n), we may estimate that τ~k(n)⩽Nk⋆ through the following reasoning: for even k, consider a⩽Nk⋆ (see Definition 4). If b⩽Nk⋆, then (pb,pa)k=1 for at most Nk⋆-1 such b (excluding b=a). If b>Nk⋆, then (pb,pa)k=1 for at most 1 such b (the case of Dk(pa)={1,pa} and b=2a>Nk⋆, as here Dk(pb)=D2(pb)). Thus, τ~k(pa)⩽Nk⋆ for a⩽Nk⋆. For a>Nk⋆, Dk(pa)=D2(pa), and so (pb,pa)k=1 for at most 2 such b by the above comments.
For oddk, a similar argument gives (pb,pa)k>1 for at most Nk⋆ choices of b when a⩽Nk⋆, and precisely 2 choices of b when a>Nk⋆; namely, b=0 and b=a. So Nk⋆ bounds τ~k(pa) for all a.
Now,τk(p)=2 for all k, and for some Bk⩽Nk⋆, 2Bk⩾Nk⋆⩾τ~k(n). Thus, since τk(pa)⩾2 for all a>0, we have that τk(n)Bk⩾τ~k(n). In particular, there is a least Bk such that, for all n, τk(n)Bk⩾τ~k(n). We will use this Bk in our asymptotic estimates.We immediately get the following result as a consequence of Theorem6.Corollary 8.
φ k , r ( x , n ) = ( x r / ( r + 1 ) ) φ k , 0 ( x , n ) for r∈N.Proof.
The caser=0 is trivially true. We prove for each r>0 using Stieltjes Integration. Then (20)∑m⩽xm,nk=1mr+Oxr=r∫0x∑m⩽ym,nk=1mr-1dy=r∫0xyrφnnKkn+Oyr-1Ekndy=xr+1r+1φnnKkn+OxrEkn=xrr+1φk,0x,n,where the error term from the integral is absorbed by O(xrEk(n)).Theorem 9.
Letk⩾0. Suppose that an arithmetical function f is of the form (21)fn=∑dkngdndr,with k>0 and r∈N and g(n) is O(ns), with s⩽r-1. Then (22)∑n⩽xfn=xr+1r+1∑n=1∞gnLknnr+1+Oxrlog⁡xBk+2Proof.
Letk, r, and s be given. Then (23)∑n⩽xfn=∑n⩽x∑dk+1ngdndr=∑n⩽x∑dd′=nd,d′k=1gdndr=∑dd′⩽xd,d′k=1gdndr==∑d⩽xgd∑d′⩽x/dd,d′k=1d′r=∑d⩽xgdφk,rxd,d=∑d⩽xgdφk,rxd,d==xr+1r+1∑d⩽xgdLkddr+1+O∑d⩽xxrgdEkddr.
By our remark above, we may findBk such that τ~k(n)⩽(τk(n))Bk for all n, which enables us to estimate (24)Oxr∑n⩽xgnEknnr⩽Oxr∑n⩽xτnBk+2n=Oxrlog⁡xBk+2,where we use the fact that g is O(ns) with s⩽r-1. Also, (25)xr+1r+1∑n⩽xgnLknnr+1=xr+1r+1∑n=1∞gnLknnr+1-xr+1r+1∑n>xgnLknnr+1,and since g is O(ns) and Lk(n) is bounded, the infinite sums converge, but (26)xr+1r+1∑n>xgnLknnr+1=Oxs+1,and s<r, so this is absorbed into our error term and we have our result.Note that, for eachk and for all ϵ>0, we may state our error term for the summatory function as O(xr+ϵ), where the multiplicative constant implied by the Big-Oh notation depends only on ϵ and k. This enables us to achieve roughly the same error as Cohen [7], albeit not as asymptotically strong as xr(log⁡x)Bk. However, as k tends to infinity, our error becomes unbounded, and so we cannot achieve Cohen’s result for the infinitary case.We recall thatμk, the k-ary analogue of the Möbius function, is defined recursively via (27)μkp0=1,∑pbkpaμkpb=0,which is extended to all n by making μk multiplicative. We then have the following.Lemma 10.
Letk be given. Then there is a constant Ck depending only on k such that, for each k, μkn⩽τ(n)Ck.Proof.
By Theorem3, for each prime p and each k, there is an Nk⋆ that ensures Dk(pa)=D1(pa) or D2(pa), depending on the parity of k, for all a>Nk⋆. The values of μkpa for a⩽2Nk⋆ are finite, being generated from a finite recursion. For odd k with a>Nk⋆, μk(pa)=-1. For even k and even a, with a>2Nk⋆+1,(28)-μkpa=∑pbkpab≠aμkpb=∑pbkpa-1μkpb-μkpa/2,since Dk(pa)=D2(pa) and Dk(pa-1)=D2(pa-1)=D(pa-1), as a-1 is odd. But (29)∑pbkpa-1μkpb=0,so μk(pa)=μk(pa/2). Also, (30)-μkpa+1=∑pbkpa+1b≠a+1μkpb=∑pbkpaμkpb+μkpa/2=μkpa/2,so(31)μkpa=μkpa/2=-μkpa+1for even a. Hence, μk(pa) is bounded in absolute value for each k—call this bound 2Ck—and so μkn⩽2Ckω(n)=τ1(n)Ck⩽τ(n)Ck and we are done.We will analyze the summatory functions for thek-ary analogues of several well-known families of arithmetical functions:(i)
Thek-ary divisor sum functions: (32)σk,rn≔∑dkndr(ii)
Thek-ary Jordan totient functions: (33)Jk,rn≔∑dknμknddr(iii)
Thek-ary Dedekind functions: (34)ψk,rn≔∑dknμknddrHerer denotes a positive integer. By Lemma 10, we may apply Theorem 9 to the Jordan and Dedekind functions of order r>0 without issue, since μk(n) is logarithmic in n; the summatory functions for the divisor sum functions carry no special restriction on r aside from it being a positive integer:(i)
(35)Sσk,rx=xr+1r+1∑n=1∞Lknnr+1+Oxrlog⁡xBk(ii)
(36)SJk,rx=xr+1r+1∑n=1∞μknLknnr+1+Oxrlog⁡xBk(iii)
(37)Sψk,rx=xr+1r+1∑n=1∞μknLknnr+1+Oxrlog⁡xBkBy Theorems2 and 3, for each n, the sequence {L2k(n)}k=0∞ (resp., {L2k+1(n)}k=0∞) is monotonically increasing (resp., decreasing). Both sequences must have the same limit, L∞(n), which one can identify with the function K∞(n) from Cohen’s manuscript. However, we cannot obtain the function φ∞,0(x,n) via a limit as k tends to infinity of φk,0(x,n), as the error term grows without bound in k. A new approach will likely be needed in order to unify the infinite case with the finite cases.



---

*Source: 9349245-2018-06-03.xml*