§27.2 Functions

§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=\prod_{r=1}^{\nu\left(n\right)}p^{a_{r}}_{r},$ ⓘ Symbols: $\nu\left(\NVar{n}\right)$: number of distinct primes dividing a number, $n$: positive integer, $p,p_{1},\ldots$: prime numbers and $a$: primitive root Referenced by: §27.2(i), §27.3 Permalink: http://dlmf.nist.gov/27.2.E1 Encodings: TeX, pMML, png See also: Annotations for §27.2(i), §27.2 and Ch.27

where $p_{1},p_{2},\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\leq x$:

 27.2.2 $\pi\left(x\right)=\sum_{p\leq x}1.$ ⓘ Defines: $\pi\left(\NVar{x}\right)$: number of primes not exceeding a number Symbols: $p,p_{1},\ldots$: prime numbers and $x$: real number Permalink: http://dlmf.nist.gov/27.2.E2 Encodings: TeX, pMML, png See also: Annotations for §27.2(i), §27.2 and Ch.27

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

 27.2.3 $\pi\left(x\right)\sim\frac{x}{\ln x}.$ ⓘ Symbols: $\sim$: asymptotic equality, $\ln\NVar{z}$: principal branch of logarithm function, $\pi\left(\NVar{x}\right)$: number of primes not exceeding a number and $x$: real number Referenced by: §25.16(i), §27.11 Permalink: http://dlmf.nist.gov/27.2.E3 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.2(i), §27.2 and Ch.27

(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\infty$:

 27.2.4 $p_{n}\sim n\ln n.$ ⓘ Symbols: $\sim$: asymptotic equality, $\ln\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $p,p_{1},\ldots$: prime numbers Permalink: http://dlmf.nist.gov/27.2.E4 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.2(i), §27.2 and Ch.27

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

 27.2.5 $\left\lfloor\frac{1}{n}\right\rfloor=\begin{cases}1,&n=1,\\ 0,&n>1.\end{cases}$ ⓘ Symbols: $\left\lfloor\NVar{x}\right\rfloor$: floor of $x$ and $n$: positive integer Referenced by: §27.5 Permalink: http://dlmf.nist.gov/27.2.E5 Encodings: TeX, pMML, png See also: Annotations for §27.2(i), §27.2 and Ch.27
 27.2.6 $\phi_{k}\left(n\right)=\sum_{\left(m,n\right)=1}m^{k},$

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

 27.2.7 $\phi\left(n\right)=\phi_{0}\left(n\right).$ ⓘ Defines: $\phi\left(\NVar{n}\right)$: Euler’s totient Symbols: $n$: positive integer Permalink: http://dlmf.nist.gov/27.2.E7 Encodings: TeX, pMML, png See also: Annotations for §27.2(i), §27.2 and Ch.27

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

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

 27.2.8 $a^{\phi\left(n\right)}\equiv 1\pmod{n},$ ⓘ Symbols: $\phi\left(\NVar{n}\right)$: Euler’s totient, $\equiv$: modular equivalence, $n$: positive integer and $a$: primitive root A&S Ref: 24.3.2 II.B Referenced by: §27.16, §27.8 Permalink: http://dlmf.nist.gov/27.2.E8 Encodings: TeX, pMML, png See also: Annotations for §27.2(i), §27.2 and Ch.27

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

 27.2.9 $d\left(n\right)=\sum_{d\mathbin{|}n}1$ ⓘ Symbols: $d_{\NVar{k}}\left(\NVar{n}\right)$: divisor function, $d$: positive integer and $n$: positive integer A&S Ref: 24.3.3 I.A Permalink: http://dlmf.nist.gov/27.2.E9 Encodings: TeX, pMML, png See also: Annotations for §27.2(i), §27.2 and Ch.27

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.

 27.2.10 $\sigma_{\alpha}\left(n\right)=\sum_{d\mathbin{|}n}d^{\alpha},$ ⓘ Defines: $\sigma_{\NVar{\alpha}}\left(\NVar{n}\right)$: sum of powers of divisors of a number Symbols: $d$: positive integer, $n$: positive integer and $\alpha$: parameter A&S Ref: 24.3.3 I.A Referenced by: §27.14(ii) Permalink: http://dlmf.nist.gov/27.2.E10 Encodings: TeX, pMML, png See also: Annotations for §27.2(i), §27.2 and Ch.27

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)$.

 27.2.11 $J_{k}\left(n\right)=\sum_{\left(\left(d_{1},\dots,d_{k}\right),n\right)=1}1,$ ⓘ Defines: $J_{\NVar{k}}\left(\NVar{n}\right)$: Jordan’s function Symbols: $\left(\NVar{m},\NVar{n}\right)$: greatest common divisor (gcd), $d$: positive integer, $k$: positive integer and $n$: positive integer Referenced by: §27.2(i) Permalink: http://dlmf.nist.gov/27.2.E11 Encodings: TeX, pMML, png See also: Annotations for §27.2(i), §27.2 and Ch.27

is the number of $k$-tuples of integers $\leq n$ whose greatest common divisor is relatively prime to $n$. This is Jordan’s function. Note that $J_{1}\left(n\right)=\phi\left(n\right)$.

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

 27.2.12 $\mu\left(n\right)=\begin{cases}1,&n=1,\\ (-1)^{\nu\left(n\right)},&a_{1}=a_{2}=\dots=a_{\nu\left(n\right)}=1,\\ 0,&\mbox{otherwise}.\end{cases}$ ⓘ Defines: $\mu\left(\NVar{n}\right)$: Möbius function Symbols: $\nu\left(\NVar{n}\right)$: number of distinct primes dividing a number, $n$: positive integer and $a$: primitive root A&S Ref: 24.3.1 I.A Permalink: http://dlmf.nist.gov/27.2.E12 Encodings: TeX, pMML, png See also: Annotations for §27.2(i), §27.2 and Ch.27

This is the Möbius function.

 27.2.13 $\lambda\left(n\right)=\begin{cases}1,&n=1,\\ (-1)^{a_{1}+\dots+a_{\nu\left(n\right)}},&n>1.\end{cases}$ ⓘ Defines: $\lambda\left(\NVar{n}\right)$: Liouville’s function Symbols: $\nu\left(\NVar{n}\right)$: number of distinct primes dividing a number, $n$: positive integer and $a$: primitive root Permalink: http://dlmf.nist.gov/27.2.E13 Encodings: TeX, pMML, png See also: Annotations for §27.2(i), §27.2 and Ch.27

This is Liouville’s function.

 27.2.14 $\Lambda\left(n\right)=\ln p,$ $n=p^{a}$, ⓘ Defines: $\Lambda\left(\NVar{n}\right)$: Mangoldt’s function Symbols: $\ln\NVar{z}$: principal branch of logarithm function, $n$: positive integer, $p,p_{1},\ldots$: prime numbers and $a$: primitive root Permalink: http://dlmf.nist.gov/27.2.E14 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.2(i), §27.2 and Ch.27

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

§27.2(ii) Tables

Table 27.2.1 lists the first 100 prime numbers $p_{n}$. Table 27.2.2 tabulates the Euler totient function $\phi\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$.