Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

1.2: Arithmetic Functions

( \newcommand{\kernel}{\mathrm{null}\,}\)

The next topic we shall consider is that of arithmetic functions. These form the main objects of concern in number theory. We have already mentioned two such functions of two variables, the g.c.d. and l.c.m. of m and n, denoted by (m,n) and [m,n] respectively, as well as the functions c(n) and p(n). Of more direct concern at this stage are the functions

π(n)=pn1the number of primes n not exceeding n;w(n)=p|n1the number of distinct primes factors of n;ω(n)=pn1the number of primes n not exceeding n;Ω(n)=pin1the number of prime factors of n;τ(n)=d|n1the number of divisors n;σ(n)=d|ndthe sum of the divisors of nφ(n)=(a,n)=11an1the Euler totient function;

the Euler totient function counts the number of integers n and relatively prime to n.

In the section we shall be particularly concerned with the functions τ(n), σ(n), and φ(n). These have the important property that if

n=ab and (a,b)=1

then

f(ab)=f(a)f(b).

Any function satisfying this condition is called weakly multiplicative, or simply multiplicative.

A generalization of τ(n) and σ(n) is afforded by

σk(n)=d|ndk. then the sum of the kth powers of the divisors of n,

since σ0(n)=τ(n) and σ1(n)=σ(n).

The φ function can also be generalized in many ways. We shall consider later the generalization due to Jordan, φk(n)= number of k-tuples n whose g.c.d. is relatively prime to n. We shall derive some elementary properties of these and closely related functions and state some special solved and unsolved problems concerning them. We shall then discuss a theory which gives a unified approach to these functions and reveals unexpected interconnections between them. Later we shall discuss the magnitude of these functions. The functions ω(n), Ω(n), and, particularly, π(n) are of a different nature and special attention will be given to them.

Suppose in what follows that the prime power factorization of n is given by

n=pα11pα22pαss or briefly n=pα.

We note that 1 is not a prime and take for granted the provable result that, apart from order, the factorization is unique.

In terms of this factorization the functions σk(n) and φ(n) are easily determined. It is not difficult to see that the terms in the expansion of the product

p|n(1+pk+p2k++pαk)

are precisely the divisors of n raise to the \(k^{\text{th}\) power. Hence we have the desired expansion for σk(n). In particular

τ(n)=σ0(n)=(α+1),

and

σ(n)=σ1(n)=p|n(1+p+p2++pα)=p|npα+11p1,

e.g., 60=223151,

τ(60)=(2+1)(1+1)(1+1)=322=12,

σ(60)=(1+2+22)(1+3)(1+5)=746=168.

These formulas reveal the multiplicative nature of σk(n).

To obtain an explicit formula for φ(n) we make use of the following well-known combinatorial principle.

The principle of inclusion and exclusion

Given N objects each of which which may or may not possess any of the characteristics

A1,A2,....

Let N(Ai,Aj,...) be the number of objects having the characteristics Ai,Aj,... and possibly. othes. Then the number of objects which have none of these properties is

NN(Ai)+i<jN(Ai,Aj)i<j<kN(Ai,Aj,Ak)+,

where the summation is extended over all combinations of the subscripts 1, 2, ... , n in groups of one, two, three and so on, and the signs of the terms alternate.

An integer will be relatively prime to n only if it is not divisible by any of the prime factors of n. Let A1,A2,...,As denote divisibility by p1,p2,...,ps respectively. Then, according to the combinatorial principle stated above

φ(n)=ninpi+i<jnpipji<j<knpipjpk+.

This expression can be factored into the form

φ(n)=np|n(11p),

e.g.

φ(60)=60(112)(113)(115)=60122345.=16.

A similar argument shows that

φk(n)=nkp|n(11pk).

The formula for φ(n) can also be written in the form

φ(n)=nd|nμ(d)d,

where μ(d) takes on the values 0, 1, −1. Indeed μ(d)=0 if d has a square factor, μ(1)=1, and μ(p1p2ps)=(1)s. This gives some motivation for defining a function μ(n) in this way. This function plays an unexpectedly important role in number theory.

Our definition of μ(n) reveals its multiplicative nature, but it it still seems rather artificial. It has however a number of very important properties which can be used as alternative definitions. We prove the most important of these, namely

d|nμ(d)={1ifn=1,0ifn1.

Since μ(d)=0 if d contains a squared factor, it suffices to suppose that n has no such factor, i.e., n=p1p2ps. For such an n>1

d|nμ(d)=1(n1)+(n2)=(11)n=0.

By definition μ(1)=1 so the theorem is proved.

If we sum this result over n=1,2,...,x, we obtain

xd=1[xd]μ(d)=1,

which is another defining relation.

Another very interesting defining property, the proof of which I shall leavepage18image46663504as an exercise, is that if

M(x)=d=1xμ(d)

then

xd=1M([xd])=1.

This is perhaps the most elegant definition of μ. Still another very important property is that

(n=11ns)(n=1μ(n)ns)=1.

We now turn our attention to Dirichlet multiplication and series.

Consider the set of arithmetic functions. These can be combined in various ways to give new functions. For example, we could define f+g by

(f+g)(n)=f(n)+g(n)

and

(fg)(n)=f(n)g(n)

A less obvious mode of combination is given by f×g, defined by

(f×g)(n)=d|nf(d)g(nd)=dd=nf(d)g(d).

This may be called the divisor product or Dirichlet product.

This motivation for this definition os as follows. If

F(s)=n=1f(n)ns, F(s)=n=1g(n)ns, and F(s)G(s)=n=1h(n)ns,

then it is readily checked that h=f×g. Thus Dirichlet multiplication of arithmetic functions corresponds to the ordinary multiplication of the corresponding Dirichlet series:

f×g=g×f, (f×g)×h=f×(g×h),

i.e., our multiplication is commutative and associative. A purely arithmetic proof of these results is easy to supply.

Let us now define the function

=(n):1,0,0,....

It is easily seen that f×=f. Thus the function ell is the unity of our multiplication.

It can be proved without difficulty that if f(1)0, then f has an inverse with repect to ell. Such functions are called regular. Thus the regular functions form a group with respect to the operation ×.

Another theorem, whose proof we shall omit, is that the Dirichlet product of multiplicative functions is again multiplicative.

We now introduce the functions

Ik:1k,2k,3k,....

It is interesting that, starting only with the functions and Ik, we can build up many of the arithmetic functions and their important properties.

To begin with we may define μ(n) by μ=I10. This means, of course, that μ×I0= or

d|nμ(d)=(n).

and we have already seen that this is a defining property of the μ function. We can define σk by

σk=I0×Ik.

This means that

σk(n)=d|n(dk1),

which corresponds to our earlier definition. Special cases are

τ=I0×I0=I20 and σ=I0×I1

Further, we can define

φk=μ×Ik=I10×Ik.

This means that

φk(n)=d|nμ(d)(nd)k,

which again can be seen to correspond to our earlier definition.

The special case of interest here is

φ=φ1=μ×I1.

Now, to obtain some important relations between our functions, we note the so-called M¨obius inversion formula. From our point of view this says that

g=f×I0f=u×g

This is, of course, quite transparent. Written out in full it states that

g(n)=d|nf(d)f(n)=d|nμ(d)g(nd).

In this form it is considerably less obvious.

Consider now the following applications. First

σk=I0×IkIk=μ×σk.

This means that

d|nμ(d)σk(nd)=nk.

Important special cases are

d|nμ(d)τ(nd)=1,

and

d|nμ(d)σ(nd)=1.

Again

φk=I10×IkIk=I0×φk,

so that

d|nφk(d)=nk,

We can obtain identities of a somewhat different kind. Thus

σk×φk=I0×Ik×I10×Ik=Ik×Ik,

and hence

d|nσk(d)φk(nd)=d|ndk(nd)k=d|nnk=τ(n)nk.

A special case of interest here is

d|nσ(d)φ(nd)=nτ(n).

In order to make our calculus applicable to problems concerning distribution of primes, we introduce a unary operation on our functions, called differentiation:

f(n)=f(n) log n

The motivation for this definition can be seen from

dds(f(n)ns)=(logn)f(n)ns.

Now let us define

Λ(n)={logpifn=pα,0ifnpα.

It is easily seen that

d|nΛ(d)=logn

In our Dirichlet multiplication notation we have

Λ×I0=I0,

so that

Λ=I10×(I0)=μ×(I0)

or

Λ(n)=d|nμ(d) log (nd)=d|nμ(d) log d.

Let us now interpret some of our results in terms of Dirichlet series. We have the correspondence

F(s)f(n) if F(s)=f(n)ns,

and we know that Dirichlet multiplication of arithmetic functions corresponds to ordinary multiplication for Dirichlet series. We start with

fF,11, and I0ζ(s).

Furthermore

Ikn=1nkns=ζ(sk).

Also

μ1ζ(s) and I0 log nns=ζ(s).

This yields

σk(n)ns=ζ(s)ζ(sk).

Special cases are

τ(n)ns=ζ2(s)

and

σ(n)ns=ζ(s)ζ(s1).

Again

\(\sum \dfrac{\mu(n){n^s) = \dfrac{1}{\zeta(s)}\)

and

φk(n)ns=ζ(sk)ζ(s),

with the special case

φ(n)ns=ζ(s1)ζ(s).

To bring a few of these down to quite numerical results we have

τ(n)n2=ζ2(2)=π436,σ4(n)n2=ζ(2)ζ(4)=π26π490=π6540.μ(n)n2=6π2

As for our Λ function, we had

Λ=I10×I0;

this means that

n=1Λ(n)ns=ζ(s)ζ(s).

The prime number theorem depends on going from this to a reasonable estimate for

Ψ(x)=xn=1Λ(n).

Indeed we wish to show that Ψ(x)x.

Any contour integration with the right side of (1) involves of course the need for knowing where ζ(s) vanishes. This is one of the central problems of number theory.

Let us briefly discuss some other Dirichlet series.

If n=pα11pα22pαss define

λ(n)=(1)α1+α2++αs.

The λ function has properties similar to those of the μ function. We leave as an exercise to show that

d|nλ(d)={1if n=r2.0if nr2.

Now

ζ(2s)=s(n)ns where s(n)={1if n=r2.0if nr2.

Hence λ×I0=s, i.e.,

λ(n)nsζ(s)=ζ(2s)

or

λ(n)ns=ζ(2s)ζ(s).

For example

λ(n)n2=π490/π26=π215.

We shall conclude with a brief look at another type of generating series, namely Lambert series. These are series of the type

f(n)xn1xn.

It is easily shown that if F=f×I0 then

f(n)xn1xn=F(n)xn.

Interesting special cases are

f=I0,xn1xn=τ(n)xn;

f=μ,μ(n)xn1xn=x;

f=φ,φ(n)xn1xn=nxn=x(1x)2.

For example, taking x=110 in the last equality, we obtain

φ(1)9+φ(2)99+φ(3)999+=1081.

Exercise 1.2.1

Prove that n=1μ(n)xn1+xn=x2x2.

Prove that n=1λ(n)xn1xn=n=1xn2.

Answer

Add texts here. Do not delete this text first.


This page titled 1.2: Arithmetic Functions is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Leo Moser (The Trilla Group) via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?