# Combinatorial Aspects of the Generalized Euler's Totient

Authors: Nittiya Pabhapote; Vichian Laohakosol
Journal: International Journal of Mathematics and Mathematical Sciences
 (2010)

---

## Abstract

A generalized Euler's totient is defined as a Dirichlet convolution of a power function and a product of the Souriau-Hsu-Möbius function with a completely multiplicative function. Two combinatorial aspects of the generalized Euler's totient, namely, its connections to other totients and its relations with counting formulae, are investigated.


---

## Body

## 1. Introduction

Let𝒜 be the unique factorization domain of arithmetic functions [1, 2] equipped with addition and (Dirichlet) convolution defined, respectively, by (1.1)(f+g)(n)=f(n)+g(n),(f*g)(n)=∑ij=nf(i)g(j).
The convolution identity I∈𝒜 is defined by (1.2)I(n)={1,ifn=1,0,ifn>1.
For f∈𝒜, write f-1 for its convolution inverse whenever it exists. A nonzero arithmetic function f is said to be multiplicative if f(mn)=f(m)f(n)whenevergcd(m,n)=1, and is called completely multiplicative if this equality holds for all m,n∈ℕ. For α∈ℂ, the Souriau-Hsu-Möbius (SHM) function ([3, 4], [5, page 107]) is defined by (1.3)μα(n)=∏p∣n(ανp(n))(-1)νp(n),
where n=∏pνp(n) denotes the unique prime factorization of n∈ℕ,νp(n) being the largest exponent of the prime p that divides n. This function generalizes the usual Möbius function, μ, because μ1=μ. Note that (1.4)μ0=I,μ-1=uthearithmeticunitfunctiondefinedbyu(n)=1(n∈ℕ),
and for α,β∈ℂ, we have (1.5)μα+β=μα*μβ.
It is easily checked that μα is multiplicative; there are exactly two SHM functions that are completely multiplicative, namely, μ0=I and μ-1=u, and there is exactly one SHM function whose convolution inverse is completely multiplicative, namely, μ1=u-1. For a general reference on the Möbius function and its generalizations, see Chapter 2 of the encyclopedic work [5].The classicalEuler's totientϕ(n) is defined as the number of positive integers a≤n such that gcd(a,n)=1. It is well known (page 7 of [1]) that (1.6)ϕ(n)=∑d∣ndμ(nd)=n∏p∣n(1-1p).
For a general reference about Eulier's totient, its many facets and generalizations, see [5, Chapter 3]. Euler's totient has been given a good deal of generalizations. Of interest to us here is the one due to Wang and Hsu [6], defined for k,r∈ℕ and completely multiplicative f∈𝒜 by (1.7)ϕτ(k)(n)=∑d∣n(nd)kf(d)μr(d),
where τ=μrf. In [6] it is shown that ϕτ(k) possesses properties extending those of the classical Euler totient, such as the following.  (P1)
ϕτ(k)(n)=nk∏p∣n(1-f(p)/pk)r when n is r-powerful, that is, νp(n)≥r for each prime factor p of n.(P2)
Leta⃗:=(a1,…,ak)∈ℤk (Theorem 2.3 of [6]). Then, for prime p, there uniquely exists an r×k matrix Bp(a⃗) over ℤp:={0,1,…,p-1} such that a⃗≡(1,p,…,pr-1)Bp(a⃗)(modpr). Let Ap be a subset of ℤpk. Then, there uniquely exists a completely multiplicative f∈𝒜 with f(p) being defined by the number of vectors in Ap. For a⃗∈ℤnk, we write (a⃗,n)A=1, if no row of Bp(a⃗) is in Ap for every prime divisor p of n. Then for n being r-powerful, ϕτ(k)(n) counts the number of k-vectors a⃗:=(a1,…,ak)∈ℤnk such that (a⃗,n)A=1.We take off from the work of Wang and Hsu, by defining ourgeneralized Euler totient (or GET for short) as (1.8)ϕs,αf(n):=(ζs*μαf)(n)=∑d∣n(nd)sf(d)μα(d),
where α∈ℂ,s∈ℝ,ζs(n)=ns,ζ0=u, and f is a completely multiplicative function. Comparing with the terminology of Wang-Hsu, we see that ϕk,rf=ϕτ(k)(τ=μrf). For brevity write (1.9)ϕs,α:=ϕs,αu,ϕα:=ϕ1,α.
There have appeared quite a number of results related to our GET, such as those in [4, 6–9], and the most complete collection to date can be found in [5, Chapter 3]. In the present paper, we consider two aspects of the GET. In the next section, its relations with other totients are investigated. Here we deal mostly with those results closely connected to our GET; for further and more complete collection up to 2004, we refer to the encyclopedic work in [5, Chapter 3]. In the last section, after proving a general inversion formula, various counting formulae related to the GET are derived.Before listing a few properties of our GET generalizing the classical Euler's totient, we recall some auxiliary notions. Thelog-derivation, [10], is the operator D:𝒜→𝒜 defined by (1.10)(Df)(n)=f(n)logn(n∈ℕ).
For f∈𝒜,f(1)>0, the Rearick logarithmic operator of f (or logarithm of f; [11–13]), denoted by Logf∈𝒜, is defined via (1.11)(Logf)(1)=logf(1),(Logf)(n)=1logn∑d∣nf(d)f-1(nd)logd=1logn(Df*f-1)(n)(n>1),
where D denotes the log-derivation. For h∈𝒜, the Rearick exponential Exp h is defined as the unique element f∈𝒜,f(1)>0 such that h=Logf. For f∈𝒜,f(1)>0 and α∈ℝ, the αth power function is defined as (1.12)fα=Exp(αLogf).
It is not difficult to check that this agrees with the usual power function, should α be integral. From [11], we know that if f is multiplicative and α∈ℝ∖{0}, then fα is also multiplicative; the fact which automatically implies its converse.Proposition 1.1.
Lets∈ℝ,α∈ℂ, and f be a completely multiplicative function.  (A)
We have the product representation(1.13)ϕs,αf(n)=ns∏p∣n∑i=0νp(n)(-1)i(αi)(f(p)ps)i(n∈ℕ).(B)
Ifα∈ℝ, then ζs=ϕs,αf*fα.(C)
Ifr∈ℕ, then ϕs,αf(r)=det[Aij]r×r, where
(1.14)Aij={1,ifj∣i,1≤j≤r-1,0,ifj∤i,1≤j≤r-1,∑d∣iϕs,αf(d),ifj=r.Proof.
Part (A) follows immediately fromϕs,αf being multiplicative. Part (B) follows from the fact that μαf=f-α [14]. To prove Part (C), let B(r)=[Bij]r×r, where
(1.15)Bij={1ifj∣i,0ifj∤i.
Then
(1.16)[B11B12⋯B1rB21B22⋯B2r⋮Br1B22⋯Brr][ϕs,αf(1)ϕs,αf(2)⋮ϕs,αf(r)]=[10⋯011⋯0⋮11⋯1][ϕs,αf(1)ϕs,αf(2)⋮ϕs,αf(r)]=[∑d∣1ϕs,αf(d)∑d∣2ϕs,αf(d)⋮∑d∣rϕs,αf(d)].
Considering (1.16) as a system of simultaneous equations in the unknowns ϕs,αf(1),ϕs,αf(2),…,ϕs,αf(r) and appealing to Cramer's rule, the result follows.Part (C) generalizes a well-known identity on page 86 of [2], which is the case where f=u,s=α=1, stating that (1.17)ϕ(r)=det[aij]r×r,
where (1.18)aij={1,ifj∣i,1≤j≤r-1,0,ifj∤i,1≤j≤r-1,i,ifj=r.


## 2. Connections with Other Totients

Case I (f=u).
When the parameterss and α take integer values, the GET does indeed represent a number of well-known arithmetic functions, namely,
(2.1)ϕ1,1=ζ*μ=ϕ(theclassicalEulertotient),ϕ0,-1=u*u=σ0=τ(thenumberofdivisorsfunction),ϕs,-1=ζs*u=σs(thesumofthesthpowerofdivisorsfunction).
When s∈ℕ and α=1, this particular totient ϕs,1=ζs*μ is equivalent to quite a few classical totients.  (i.1)
The Jordan totientJs(n) which counts the number of s-tuples (x1,…,xs) such that 1≤x1,…,xs≤n and gcd(x1,…,xs,n)=1 ([1, page 13], [5, pages 186-187, page 275], [2, page 91]). Clearly, J1=ϕ. From [5, pages 186-187], closely resembles the Jordan totient is the function
(2.2)Js′(n)=#{(x1,…,xs):1≤x1≤x2≤⋯≤xs≤n,gcd(x1,…,xs,n)=1}.
While Js(n)=∑d∣nμ(d)(n/d)s, one has, on the other hand, Js′(n)=∑d∣nμ(n/d)(d+s+1s), showing that Js′ is not of the form of our GET. Even more general is the Shonhiwa's totient, Jsm [5, pages 187, 276], defined as the number of s-tuple (x1,…,xs) such that 1≤x1,…,xs≤n and gcd(x1,…,xs,m)=1, whose representation is Jsm(n)=∑d∣mμ(d)[n/d]s.(i.2)
The von Sterneck function, [1, pages 14-15] and [5, pages 275-276],
(2.3)Hs(n):=∑lcm(e1,…,es)=nϕ(e1)⋯ϕ(es),
where the sum is over all ordered s-tuples (e1,…,es)∈ℤs such that 1≤ei≤n(i=1,…,s) and lcm(e1,…,es)=n.(i.3)
Eckford Cohen's totientEs(n) which counts the number of elements of a s-reduced residue system (mod n). For integers a,b not both 0, let
(2.4)(a,b)sdenotethelargeststh-powercommondivisorofaandb.
If (a,b)s=1, we say that a and b are relatively s-prime. We refer to the subset of a complete residue system M (mod ns) consisting of all elements of M that are relatively s-prime to ns as a s-reduced residue system (mod n), [2, pages 98-99] and [5, pages 275-276].(i.4)
ϕs,1(n)=Φs(ns), where Φ(n) is the Klee's totient, [15], which counts the number of integers h∈{1,2,…,n} for which gcd(h,n) is sth-power-free, that is, contains no sth-power divisors other than 1. The Klee's totient has a product representation of the form, [5, page 278], Φs(n)=n∏ps∣n(1-1/ps).(i.5)
Haukkanen's totient, [5, page 276], ϕkm,1(n)=∑d∣ndkmμ(d), which counts the number of m-tuples (x1,…,xm) mod nk such that (gcd(x1,x2,…,xm),nk)k=1.
On the other hand, based on the combinatorial interpretation (P2) ofϕs,α above, our GET includes several special totients [6] such as taking α=1 and
(i)
Bp(a⃗)=ℤp when p≤k, or Bp(a⃗)=ℤk when p>k, we obtain Schemmel's totient, Sk(n), which counts the number of sets of k consecutive integers each less than n and relatively prime to n. The function Sk(n) has a product representation of the form Sk(n)=n∏p∣n(1-k/p), [5, page 276]. The case k=2 was also called Schemmel totient function and was shown by Lehmer to have application in the enumeration of certain magic squares, [5, page 184]. There are many other totients closely connected to Schemmel's totient. As examples, we describe two more, taken from [5, Chapter 3], namely, Lucas's and Nageswara Rao's totients. For fixed integers e1,…,ek, Lucas's totient counts the number of integers h∈{0,1,…,n-1} such that h-e1,…,h-en are relatively prime to n and its product representation is n∏p∣n(1-λ/p), where λ is the number of distinct residues of e1,…,ek mod p. Nageswara Rao's totient counts the number of sets of k consecutive integers each less than ns which are s-prime to ns;(ii)
letF={f1(x),…,fk(x)} be a set of polynomials with integer coefficients and Bp(a⃗)={(a1,…,ak);fi(ai)≡0(modp),i=1,…,k}, we obtain Steven's totient which denotes the number of k-vectors (a1,…,ak)(modn) such that gcd(f1(a1),…,fk(ak),n)=1). Following [5, pages 279-280], the product representation of Stevens's totient takes the form nk∏j=1r(1-N1j⋯Nkj/pjk), where n=∏j=1rpjaj,Nij is the number of incongruent solutions of fi(x)≡0(modpj). The Stevens's totient is multiplicative, and contains, as special cases
(1)
the Jordan totientJk(n) (by taking f1(x)=⋯=fk(x)=x);(2)
the Schemmel totientSt(n) (by taking k=1,f1(x)=x(x+1)⋯(x+t-1));(3)
Cashwell-Everett's totient (by takingf1(x)=⋯=fℓ(x)=nx,fℓ+1(x)=⋯=fk(x)=x), which counts the number of k-tuples (a1,…,ak) with ℓ≤ak≤k such that gcd(aℓ+1,…,ak,n)=1. Its product representation is nk∏p∣n(1-pj/pk).
In passing, let us mention that, our GET is closely connected to the generalized Ramanujan sum through(2.5)ϕ1,α(r)=c(α)(n,r)wheneverr∣n([9,page4],[5,pages277-278]).Case II (f≠u).
The GET also includes a number of known totients in this case.(ii.1)
The Garcia-Ligh totient [16, 17], defined for fixed s,d∈ℕ, by
(2.6)ϕ(s,d,n):=ϕ1,1Id(n),
where Id(n):=I(gcd(d,n)) is easily shown to be completely multiplicative. This totient ϕ1,1Id(n) counts the number of elements in the set {s,s+d,…,s+(n-1)d} that are relatively prime to n with ϕ(1,1,n)≡ϕ(n).(ii.2)
The Garcia-Ligh totient is a special case of the following totient taken from Exercise1.21 on pages 34-35 of [1]. Let g(x)∈ℤ[x]. The number of integers x∈{1,2,…,n} and gcd(f(x),n)=1 is, using our terminology above,
(2.7)ϕ1,1vg(n)=(ζ1*vgμ)(n)=∑d∣ndvg(nd)μ(nd),
where vg is the completely multiplicative function defined over prime p by vg(p)=gp, the number of solutions of the congruence g(x)≡0 (mod p).(ii.3)
Martin G. Beumer's function (SectionIV.2 on pages 72–74 of [2]) defined for k∈ℕ, by
(2.8)ϕ0,1-ku=ζ0*(μ1-ku)=u*(uk-1)=uk,
where we have used a result of Haukkanen [14], that if f is a completely multiplicative function and α∈ℝ, then fα=μ-αf.(ii.4)
The Dedekindψ-function ([2, Problem 10, page 80], [5, page 284]) defined by ψ(n)=n∏p∣n(1+1/p) is clearly equivalent to
(2.9)ϕ1,1f=ζ1*μ1f,
where f is the completely multiplicative function defined for prime p by f(p)=-1.(ii.5)
H. L. Adler's totient ([2, Section V.6, page 102], [5, page 279]) is defined, for fixed N∈ℕ, as
(2.10)ϕ1,1ϵN(r)=(ζ1*μ1ϵN)(r)=r∏p∣r(1-ϵN(p)p),
where ϵN is the completely multiplicative function defined, for prime p, by
(2.11)ϵN(p)={1,ifp∣N,2,ifp∤N.
The totient value ϕ1,1ϵN(r) is the number of ordered pairs (x,y)∈ℕ2 for which x+y=N+r,gcd(x,r)=gcd(y,r)=1 and 1≤x≤r. Note that when N=0, this is merely Euler's totient.(ii.6)
D. L. Goldsmith's totient (the main theorem on page 183 of [18]) is defined, for m∈ℕ, by
(2.12)ψ(m)=#S(m)=#{x;0≤x<m,gcd(Q(x),m)=1},
where Q(x)∈ℤ[x]. From the meaning of ψ(m), it is clear that ψ(m) is a multiplicative function (Problem 5, page 31 in [19]). Thus,
(2.13)ϕ1,1f(m)=(ζ1*μ1f)(m)=ψ(m)=∏p∣m(pνp(m)-βppνp(m)-1),
where βp is the number of integers x∈{0,1,…,p-1} such that Q(x) is divisible by the prime p and f is the completely multiplicative function defined for prime p by f(p)=βp. It is possible to enlarge the values of α in the Goldsmith's totient such as taking α=2 to get
(2.14)ϕ1,2g(m)=(ζ1*μ2g)(m)=∏p∣m(pνp(m)-βppνp(m)-1),
where g is the completely multiplicative function defined for prime p by g(p)=p+p2-pβp.Letf,g∈𝒜. For k∈ℕ, define the  k-convolution of f and g by (2.15)(f*kg)(n):=∑dka=nf(d)g(a).
It is easily checked that the k-convolution is neither commutative nor associative. Yet it preserves multiplicativity, that is, if f and g are multiplicative functions, then the f*kg is also multiplicative (Problem 1.26, page 37 of [1]). The  kthconvolute(page 53 of [1]) of f∈𝒜 is defined by (2.16)f[k](n):={f(n1/k),ifnisakthpower,0,otherwise.
The k-convolution is connected to the usual (Dirichlet) convolution via (2.17)f*kg=f[k]*g.
We list here some examples of arithmetic functions which enjoy k-convolution relations.  (1)
Klee's totient,Φk(n), which counts the number of integers h∈{1,2,…,n} for which gcd(h,n) is kth-power-free, satisfies (Problem 1.29 on pages 38-39 of [1]),
(2.18)Φk(n)=(μ1*kζ1)(n)=∑dk∣nμ1(d)ndk.(2)
The number of divisors functionϕ0,-1=σ0:=τ is related to the arithmetic function θk(n) which counts the number of k-free divisors of n by (Problem 1.27, page 37 of [1])(2.19)τ(n)=∑dk∣nθk(ndk)=(u*kθ)(n).(3)
The Liouville's function is defined by(2.20)λ(1)=1;λ(n)=(-1)r1+⋯+rtifn=p1r1⋯ptrt.
It is known (Problem 1.47 on page 45 of [1]) that λ is completely multiplicative and satisfies
(2.21)λ(n)=(u*2μ1)(n)=∑d2∣nμ1(nd2).(4)
Forκ∈ℝ,t∈ℕ, the Gegenbauer's function (page 55 of [1]) is defined as
(2.22)ρκ,t(n)=∑d∣nn∣disatthpowerdκ=(u*tζκ)(n)=(u[t]*ζκ)(n).The notion of convolute enables us to give swift proofs of a number of identities such as the following ones which are generalizations of Problem1.59 on page 48, Problem 1.78 on page 51, Problem 1.89 on page 55, and Problem 1.90 on page 56 of [1].Proposition 2.1.
Lets,h,κ∈ℝ,andk,t∈ℕ. Then,  (i)
∑d∣nλ(d)ϕs,-1(n/d)=∑d2∣n(n/d2)s,(ii)
∑d2∣nϕs,1(n/d2)=∑d∣ndsλ(n/d),(iii)
∑d∣ndhρκ,t(n/d)=∑d∣ndκρh,t(n),(iv)
∑d∣ndκϕh,1(d)ρκ,t(n/d)=ρh+κ,t(n),(v)
∑d∣nρh,t(d)ρκ,t(n/d)=nκ∑dt∣nτ(d)ϕh-κ,-1(n/dt)/dκt.Proof.
We first note the identityλ*u=u[2] which follows from the facts that λ*u is multiplicative and
(2.23)(λ*u)(pk)=∑i=0kλ(pi)={1,ifkiseven,0,otherwise.
Assertion (i) follows quickly from u*2ζs=u[2]*ζs=(λ*u)*ζs=λ*ϕs,-1.
Assertion (ii) follows fromu*2ϕs,1=u[2]*ϕs,1=(λ*u)*(ζs*μ)=λ*ζs.
Assertion (iii) follows fromζh*ρκ,t=ζh*u[t]*ζκ=ρh,t*ζκ.
Assertion (iv) follows from(2.24)ζκϕh,1*ρκ,t=ζκ(ζh*μ)*(u[t]*ζκ)=(ζκ+h*u[t])*(ζκμ*ζκ)=ρκ+h,t*ζκ(μ*u)=ρκ+h,t*I.
To prove (v), we need the identity u[t]*u[t]=τ[t]. Now Assertion (v) follows from
(2.25)ρh,t*ρκ,t=(u[t]*ζh)*(u[t]*ζκ)=(u[t]*u[t])*(ζh-κ*u)ζκ=τ[t]*(ϕh-κ,-1ζκ)=τ*t(ϕh-κ,-1ζκ).


## 3. Inversion and Counting Formulae

In [20], see also Problem 1.25, pages 36-37 of [1], Suryanarayana proved the following inversion formula:(3.1)g(n)=∑dka=nf(a)⇔f(n)=∑dka=nμ(d)g(a).Our objective now is to extend this inversion formula using our GET.Theorem 3.1 (modified generalized Möbius inversion formula).
Letk,n∈ℕ and f,g∈𝒜. For α∈ℂ, one has
(3.2)g(n)=∑dka=nf(a)⇔(f*μα-1[k])(n)=∑dka=nμα(d)g(a).Proof.
Recall that the summation overdka=n, with fixed k∈ℕ, means that n is written as n=dka when a runs through all divisors of n for which n can be so written with d∈ℕ. The result follows at once from
(3.3)∑dka=nμα(d)g(a)=∑dka=nμα(d)∑skt=af(t)=∑dkskt=nμα(d)f(t)=∑t∣nf(t)∑dk∣n/tμα(d)=∑t∣nf(t)∑d∣n/tkμα(d)=∑t∣nf(t)μα-1(ntk)=∑t∣nf(t)μα-1[k](nt)=(f*μα-1[k])(n).Theorem1 of [20] is a special case of Theorem 3.1 when α=1. As is well known, the Möbius inversion formula has extensive applications which is also the case of our new inversion formula. Applying Suryanarayana's inversion formula to three examples in the last section, we obtain (3.4)∑dk∣nΦk(ndk)=n,θk(n)=∑dk∣nμ(d)τ(ndk),μ(n)=∑d2∣nμ(d)λ(nd2).
As an application to counting formulae, taking α=1,g=ζ1 in Theorem 3.1, we get the following special case of Theorem 2 in [21].Corollary 3.2.
Letr,n∈ℕ and Klee's function Tr(n) be the number of integers k such that 1≤k≤n and gcd(k,n) is not divisible by the rth power of any prime. Then,
(3.5)n=∑dr∣nTr(ndr)⇔Tr(n)=∑dr∣nμ(d)ndr.Following [5, page 136], a generalization of Klee's function Tr introduced by D. Suryanarayana is the function Tr(x,n)=∑d∣nμr(d)[x/d]; note that Tr(n,n)=Tr(n).To illustrate another application, consider a function of the form(3.6)∑st=kμ(s)mt,
which has been a subject of many investigations such as those in [22–25]. This function leads to a formula for the number of primitive elements over a finite field. Let a,N∈ℕ and let all distinct prime factors of N be p1⋯pk. Define(3.7)F(a,N)=∑d∣Nμ(d)aN/d=aN-∑iaN/pi+∑i<jaN/pipj+⋯+(-1)kaN/p1⋯pk.
It is known ([24, pages 84–86], [5, pages 191–193]) that (3.8)F(a,N)≡0(modN),
a result which generalizes Fermat's little theorem when N is prime. This congruence has been much extended in [22, 25]. Dickson [24, pages 84–86] shows a connection with Euler's totient via the identity (3.9)F(a,N)=∑d,a,Nϕ(d),
where the summation ∑d,a,N runs through proper divisors d of aN-1; by a proper divisor of aN-1 we mean a divisor of aN-1 that does not divide am-1 if  0<m<N.We aim now to extend these results even further to our GET. Fora,k,N∈ℕ and α∈ℂ, define (3.10)Fk,α(a,N):=∑dkm=Nμ(d)hα,a(k)(m),
where (3.11)hα,a(k)(m)=∑dkt=am-1ϕα(t).Theorem 3.3.
Letα∈ℂ and a,k,N∈ℕ with a>1. Then,
(3.12)Fk,α(a,N)=∑dk,a,Nϕα(t).Proof.
Let(3.13)fk,α(m)=∑dk,a,mϕα(t),H(N)=∑nkm=Nfk,α(m).
By Theorem 3.1, we have
(3.14)fk,α(N)=∑dk,a,Nϕα(t)=∑nkm=Nμ(n)H(m).
On the other hand, from the definitions of H and f, we get
(3.15)H(N)=∑nkm=N(∑dk,a,mϕα(t))=∑dkt=aj1-1dk∤am1-1m1<j1ϕα(t)+∑dkt=aj2-1dk∤am2-1m2<j2ϕα(t)+⋯+∑dkt=ajs-1dk∤ams-1ms<jsϕα(t)+∑dkt=aN-1dk∤am-1m<Nϕα(t)whenN=nkji,where0<j1<⋯<js<NarealldivisorsofNsuchthatNcanbesowrittenwithn∈ℕandi∈{1,2,…,s}=∑dkt=aN-1ϕα(t)=hα,a(k)(N).
Consequently,
(3.16)Fk,α(a,N)=fk,α(N)=∑dk,a,Nϕα(t).Specializingk=1,α=1 in Theorem 3.3, we recover the result of Dickson mentioned above, namely, (3.17)∑d,a,Nϕ(d)=F1,1(a,N)=∑d∣Nμ(d)h1,a(1)(Nd)=∑d∣Nμ(d)(ζ*I)(aN/d-1)=∑d∣Nμ(d)aN/d.
If we take a=pn, a prime power, in (3.7), then it is well known [26, page 93] that the number of monic irreducible polynomials of order m over GF(pn) is (3.18)1m∑d∣mμ(d)pnm/d=1m(pmn-∑ipnm/pi+∑i<jpnm/pipj+⋯+(-1)kpnm/p1⋯pk)
and F(pn,m)=∑d∣mμ(d)pnm/d is the number of primitive elements of GF(pnm)/GP(pn). Taking k=1,α=0 in Theorem 3.3 yields another beautiful formula (3.19)F1,0(a,N)=∑d∣Nμ(d)(ζ*μ-1)(aN/d-1)=∑d∣Nμ(d)σ(aN/d-1).Combining the results of Theorems3.1 and 3.3 yields another relation between μα and ϕα.Corollary 3.4.
Letα∈ℂ and a,k,N∈ℕ with a>1. Then,
(3.20)hα,a(k)(N)=∑dkm=Nfk,α(m)⇔(fk,α*μα-1[k])(N)=∑dkm=Nμα(d)hα,a(k)(m),
where
(3.21)hα,a(k)(m)=∑dkt=am-1ϕα(t),fk,α(m)=∑dk,a,mϕα(t).



---

*Source: 648165-2010-09-14.xml*