Functions in this section derive their properties from the fundamental theorem of arithmetic, which states that every integer can be represented uniquely as a product of prime powers,
where are the distinct prime factors of , each exponent is positive, and is the number of distinct primes dividing . ( 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 that counts the number of primes not exceeding . It can be expressed as a sum over all primes :
Gauss and Legendre conjectured that is asymptotic to as :
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 th prime (when the primes are listed in increasing order) is asymptotic to as :
(See also §27.12.) Other examples of number-theoretic functions treated in this chapter are as follows.
the sum of the th powers of the positive integers that are relatively prime to .
This is the number of positive integers that are relatively prime to ; is Euler’s totient.
If , then the Euler–Fermat theorem states that
and if is the smallest positive integer such that , then is a primitive root mod . The numbers are relatively prime to and distinct (mod ). Such a set is a reduced residue system modulo .
is the number of divisors of and is the divisor function. It is the special case of the function that counts the number of ways of expressing as the product of factors, with the order of factors taken into account.
is the sum of the th powers of the divisors of , where the exponent can be real or complex. Note that .
is the number of -tuples of integers whose greatest common divisor is relatively prime to . This is Jordan’s function. Note that .
In the following examples, are the exponents in the factorization of in (27.2.1).
This is the Möbius function.
This is Liouville’s function.
where is a prime power with ; otherwise . This is Mangoldt’s function.