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,

where $p_1,p_2,\mathrm{\dots },p_{\nu \left(n\right)}$ are the distinct prime factors of $n$, each exponent $a_r$ is positive, and $\nu \left(n\right)$ is the number of distinct primes dividing $n$. ($\nu \left(1\right)$ 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 $\pi \left(x\right)$ that counts the number of primes not exceeding $x$. It can be expressed as a sum over all primes $p\le x$:

Gauss and Legendre conjectured that $\pi \left(x\right)$ is asymptotic to $x/\ln x$ as $x\to \mathrm{\infty }$:

(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 $n$th prime $p_n$ (when the primes are listed in increasing order) is asymptotic to $n\ln n$ as $n\to \mathrm{\infty }$:

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

the sum of the $k$th powers of the positive integers $m\le n$ that are relatively prime to $n$.

This is the number of positive integers $\le n$ that are relatively prime to $n$; $\varphi \left(n\right)$ is Euler’s totient.

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

and if $\varphi \left(n\right)$ is the smallest positive integer $f$ such that $a^f\equiv 1(modn)$, then $a$ is a primitive root mod $n$. The $\varphi \left(n\right)$ numbers $a,a^2,\mathrm{\dots },a^{\varphi \left(n\right)}$ are relatively prime to $n$ and distinct (mod $n$). Such a set is a reduced residue system modulo $n$.

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

is the sum of the $\alpha$th powers of the divisors of $n$, where the exponent $\alpha$ can be real or complex. Note that ${\sigma }_0\left(n\right)=d\left(n\right)$.

is the number of $k$-tuples of integers $\le n$ whose greatest common divisor is relatively prime to $n$. This is Jordan’s function. Note that $J_1\left(n\right)=\varphi \left(n\right)$.

In the following examples, $a_1,\mathrm{\dots },a_{\nu \left(n\right)}$ are the exponents in the factorization of $n$ in (27.2.1).

This is the Möbius function.

This is Liouville’s function.

where $p^a$ is a prime power with $a\ge 1$; otherwise $\mathrm{\Lambda }\left(n\right)=0$. This is Mangoldt’s function.

Table 27.2.1 lists the first 100 prime numbers $p_n$. Table 27.2.2 tabulates the Euler totient function $\varphi \left(n\right)$, the divisor function $d\left(n\right)$ ($={\sigma }_0(n)$), and the sum of the divisors $\sigma (n)$ ($={\sigma }_1(n)$), for $n=1(1)52$.