What's New
About the Project
NIST
27 Functions of Number TheoryMultiplicative Number Theory

§27.2 Functions

Contents

§27.2(i) Definitions

Functions in this section derive their properties from the fundamental theorem of arithmetic, which states that every integer n>1 can be represented uniquely as a product of prime powers,

27.2.1 n=r=1ν(n)prar,

where p1,p2,,pν(n) are the distinct prime factors of n, each exponent ar is positive, and ν(n) is the number of distinct primes dividing n. (ν(1) is defined to be 0.) Euclid’s Elements (Euclid (1908, Book IX, Proposition 20)) gives an elegant proof that there are infinitely many primes. Tables of primes (§27.21) reveal great irregularity in their distribution. They tend to thin out among the large integers, but this thinning out is not completely regular. There is great interest in the function π(x) that counts the number of primes not exceeding x. It can be expressed as a sum over all primes px:

27.2.2 π(x)=px1.

Gauss and Legendre conjectured that π(x) is asymptotic to x/logx as x:

27.2.3 π(x)xlogx.

(See Gauss (1863, Band II, pp. 437–477) and Legendre (1808, p. 394).)

This result, first proved in Hadamard (1896) and de la Vallée Poussin (1896a, b), is known as the prime number theorem. An equivalent form states that the nth prime pn (when the primes are listed in increasing order) is asymptotic to nlogn as n:

27.2.4 pnnlogn.

(See also §27.12.) Other examples of number-theoretic functions treated in this chapter are as follows.

27.2.5 1n={1,n=1,0,n>1.
27.2.6 ϕk(n)=(m,n)=1mk,

the sum of the kth powers of the positive integers mn that are relatively prime to n.

27.2.7 ϕ(n)=ϕ0(n).

This is the number of positive integers n that are relatively prime to n; ϕ(n) is Euler’s totient.

If (a,n)=1, then the Euler–Fermat theorem states that

27.2.8 aϕ(n)1(modn),

and if ϕ(n) is the smallest positive integer f such that af1(modn), then a is a primitive root mod n. The ϕ(n) numbers a,a2,,aϕ(n) are relatively prime to n and distinct (mod n). Such a set is a reduced residue system modulo n.

27.2.9 d(n)=d|n1

is the number of divisors of n and is the divisor function. It is the special case k=2 of the function dk(n) that counts the number of ways of expressing n as the product of k factors, with the order of factors taken into account.

27.2.10 σα(n)=d|ndα,

is the sum of the αth powers of the divisors of n, where the exponent α can be real or complex. Note that σ0(n)=d(n).

27.2.11 Jk(n)=((d1,,dk),n)=11,

is the number of k-tuples of integers n whose greatest common divisor is relatively prime to n. This is Jordan’s function. Note that J1(n)=ϕ(n).

In the following examples, a1,,aν(n) are the exponents in the factorization of n in (27.2.1).

27.2.12 μ(n)={1,n=1,(-1)ν(n),a1=a2==aν(n)=1,0,otherwise.

This is the Möbius function.

27.2.13 λ(n)={1,n=1,(-1)a1++aν(n),n>1.

This is Liouville’s function.

27.2.14 Λ(n)=logp,
n=pa,

where pa is a prime power with a1; otherwise Λ(n)=0. This is Mangoldt’s function.

§27.2(ii) Tables

Table 27.2.1 lists the first 100 prime numbers pn. Table 27.2.2 tabulates the Euler totient function ϕ(n), the divisor function d(n) (=σ0(n)), and the sum of the divisors σ(n) (=σ1(n)), for n=1(1)52.

Table 27.2.1: Primes.
n pn pn+10 pn+20 pn+30 pn+40 pn+50 pn+60 pn+70 pn+80 pn+90
1 2 31 73 127 179 233 283 353 419 467
2 3 37 79 131 181 239 293 359 421 479
3 5 41 83 137 191 241 307 367 431 487
4 7 43 89 139 193 251 311 373 433 491
5 11 47 97 149 197 257 313 379 439 499
6 13 53 101 151 199 263 317 383 443 503
7 17 59 103 157 211 269 331 389 449 509
8 19 61 107 163 223 271 337 397 457 521
9 23 67 109 167 227 277 347 401 461 523
10 29 71 113 173 229 281 349 409 463 541
Table 27.2.2: Functions related to division.
n ϕ(n) d(n) σ(n) n ϕ(n) d(n) σ(n) n ϕ(n) d(n) σ(n) n ϕ(n) d(n) σ(n)
1 1 1 1 14 6 4 24 27 18 4 40 40 16 8 90
2 1 2 3 15 8 4 24 28 12 6 56 41 40 2 42
3 2 2 4 16 8 5 31 29 28 2 30 42 12 8 96
4 2 3 7 17 16 2 18 30 8 8 72 43 42 2 44
5 4 2 6 18 6 6 39 31 30 2 32 44 20 6 84
6 2 4 12 19 18 2 20 32 16 6 63 45 24 6 78
7 6 2 8 20 8 6 42 33 20 4 48 46 22 4 72
8 4 4 15 21 12 4 32 34 16 4 54 47 46 2 48
9 6 3 13 22 10 4 36 35 24 4 48 48 16 10 124
10 4 4 18 23 22 2 24 36 12 9 91 49 42 3 57
11 10 2 12 24 8 8 60 37 36 2 38 50 20 6 93
12 4 6 28 25 20 3 31 38 18 4 60 51 32 4 72
13 12 2 14 26 12 4 42 39 24 4 56 52 24 6 98