§ 27.2. Functions

Referenced by:: §27.11, §27.12, §27.16, §27.3
Permalink:: http://dlmf.nist.gov/27.2

§27.2(i)Definitions
§27.2(ii)Tables

§ 27.2(i). Definitions

Notes:: See Apostol (1976, pp. 17–38, 48, 74–80, 113). For (27.2.11) see Erdélyi et al. (1955, p. 168).
Keywords:: divisor function, Euler-Fermat theorem, Euler's totient, fundamental theorem of arithmetic, Jordan's function, Liouville's function, Mangoldt's function, Möbius function, multiplicative number theory, number-theoretic functions, number theory, prime numbers, prime number theorem, reduced residue system
Permalink:: http://dlmf.nist.gov/27.2.SS1

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},$

Defines:: $\nu\!\left(n\right)$ : number of distinct primes dividing $n$
Symbols:: $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, pMathML, png

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(x\right)$ : number of primes $\leq x$
Symbols:: $p,p_{1},\ldots$ : prime numbers and $x$ : real number
Permalink:: http://dlmf.nist.gov/27.2.E2
Encodings:: TeX, pMathML, png

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

27.2.3 $\pi\!\left(x\right)\sim\frac{x}{\mathrm{log}\, x}.$

Symbols:: $\pi\!\left(x\right)$ : number of primes $\leq x$ , $\sim$ : asymptotically equal and $x$ : real number
Referenced by:: §27.11
Permalink:: http://dlmf.nist.gov/27.2.E3
Encodings:: TeX, pMathML, png

(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 (1896b, a), 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\mathrm{log}\, n$ as $n\to\infty$ :

27.2.4 $p_{n}\sim n\mathrm{log}\, n.$

Symbols:: $\sim$ : asymptotically equal, $n$ : positive integer and $p,p_{1},\ldots$ : prime numbers
Permalink:: http://dlmf.nist.gov/27.2.E4
Encodings:: TeX, pMathML, png

(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:: $n$ : positive integer
Referenced by:: §27.5
Permalink:: http://dlmf.nist.gov/27.2.E5
Encodings:: TeX, pMathML, png

27.2.6 $\phi _{{k}}\!\left(n\right)=\sum _{{\left(m,n\right)=1}}m^{k},$

Defines:: $\phi\!\left(n\right)$ : Euler's totient function
Symbols:: $k$ : positive integer, $m$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.2.E6
Encodings:: TeX, pMathML, png

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(n\right)$ : Euler's totient function
Symbols:: $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.2.E7
Encodings:: TeX, pMathML, png

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\;\;(\textrm{mod}n),$

Defines:: $a$ : primitive root
Symbols:: $\phi\!\left(n\right)$ : Euler's totient function and $n$ : positive integer
A&S Ref:: 24.3.2 II.B
Referenced by:: §27.16, §27.8
Permalink:: http://dlmf.nist.gov/27.2.E8
Encodings:: TeX, pMathML, png

and if $\phi\!\left(n\right)$ is the smallest positive integer $f$ such that $a^{f}\equiv 1\;\;(\textrm{mod}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\divides n}}1$

Defines:: $d\!\left(n\right)$ : divisor function
Symbols:: $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, pMathML, png

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\divides n}}d^{\alpha},$

Defines:: $\sigma _{{\alpha}}\!\left(n\right)$ : sum of powers of divisors and $\alpha$ : parameter
Symbols:: $d$ : positive integer and $n$ : positive integer
A&S Ref:: 24.3.3 I.A
Referenced by:: §27.14(ii)
Permalink:: http://dlmf.nist.gov/27.2.E10
Encodings:: TeX, pMathML, png

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 _{{((d_{1},\dots,d_{k}),n)=1}}1,$

Defines:: $J_{{k}}\!\left(n\right)$ : Jordan's function
Symbols:: $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, pMathML, png

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(n\right)$ : Möbius function
Symbols:: $\nu\!\left(n\right)$ : number of distinct primes dividing $n$ , $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, pMathML, png

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(n\right)$ : Liouville's function
Symbols:: $\nu\!\left(n\right)$ : number of distinct primes dividing $n$ , $n$ : positive integer and $a$ : primitive root
Permalink:: http://dlmf.nist.gov/27.2.E13
Encodings:: TeX, pMathML, png

This is Liouville's function.

27.2.14 $\Lambda\!\left(n\right)=\mathrm{log}\, p,$ $n=p^{a}$ ,

Defines:: $\Lambda\!\left(n\right)$ : Mangoldt's function
Symbols:: $n$ : positive integer, $p,p_{1},\ldots$ : prime numbers and $a$ : primitive root
Permalink:: http://dlmf.nist.gov/27.2.E14
Encodings:: TeX, pMathML, png

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

Notes:: Tables 27.2.1 and 27.2.2 are from Abramowitz and Stegun (1964, Tables 24.9 and 24.6).
Keywords:: prime numbers
Permalink:: http://dlmf.nist.gov/27.2.SS2

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

27.2.1. Primes.

$n$	$p_{n}$	$p_{{n+20}}$	$p_{{n+40}}$	$p_{{n+60}}$	$p_{{n+80}}$
1	2	73	179	283	419
2	3	79	181	293	421
3	5	83	191	307	431
4	7	89	193	311	433
5	11	97	197	313	439
6	13	101	199	317	443
7	17	103	211	331	449
8	19	107	223	337	457
9	23	109	227	347	461
10	29	113	229	349	463
11	31	127	233	353	467
12	37	131	239	359	479
13	41	137	241	367	487
14	43	139	251	373	491
15	47	149	257	379	499
16	53	151	263	383	503
17	59	157	269	389	509
18	61	163	271	397	521
19	67	167	277	401	523
20	71	173	281	409	541

Symbols:: $n$ : positive integer and $p,p_{1},\ldots$ : prime numbers
Referenced by:: §27.2(ii), §27.2(ii)
Permalink:: http://dlmf.nist.gov/27.2.T1

27.2.2. Functions related to division.

$n$	$\phi\!\left(n\right)$	$d\!\left(n\right)$	$\sigma\!\left(n\right)$	$n$	$\phi\!\left(n\right)$	$d\!\left(n\right)$	$\sigma\!\left(n\right)$
1	1	1	1	26	12	4	42
2	1	2	3	27	18	4	40
3	2	2	4	28	12	6	56
4	2	3	7	29	28	2	30
5	4	2	6	30	8	8	72
6	2	4	12	31	30	2	32
7	6	2	8	32	16	6	63
8	4	4	15	33	20	4	48
9	6	3	13	34	16	4	54
10	4	4	18	35	24	4	48
11	10	2	12	36	12	9	91
12	4	6	28	37	36	2	38
13	12	2	14	38	18	4	60
14	6	4	24	39	24	4	56
15	8	4	24	40	16	8	90
16	8	5	31	41	40	2	42
17	16	2	18	42	12	8	96
18	6	6	39	43	42	2	44
19	18	2	20	44	20	6	84
20	8	6	42	45	24	6	78
21	12	4	32	46	22	4	72
22	10	4	36	47	46	2	48
23	22	2	24	48	16	10	124
24	8	8	60	49	42	3	57
25	20	3	31	50	20	6	93

Symbols:: $\phi\!\left(n\right)$ : Euler's totient function, $d\!\left(n\right)$ : divisor function, $\sigma _{{\alpha}}\!\left(n\right)$ : sum of powers of divisors and $n$ : positive integer
Referenced by:: §27.2(ii), §27.2(ii)
Permalink:: http://dlmf.nist.gov/27.2.T2

$n$	$p_{n}$	$p_{{n+20}}$	$p_{{n+40}}$	$p_{{n+60}}$	$p_{{n+80}}$
1	2	73	179	283	419
2	3	79	181	293	421
3	5	83	191	307	431
4	7	89	193	311	433
5	11	97	197	313	439
6	13	101	199	317	443
7	17	103	211	331	449
8	19	107	223	337	457
9	23	109	227	347	461
10	29	113	229	349	463
11	31	127	233	353	467
12	37	131	239	359	479
13	41	137	241	367	487
14	43	139	251	373	491
15	47	149	257	379	499
16	53	151	263	383	503
17	59	157	269	389	509
18	61	163	271	397	521
19	67	167	277	401	523
20	71	173	281	409	541

$n$	$\phi\!\left(n\right)$	$d\!\left(n\right)$	$\sigma\!\left(n\right)$	$n$	$\phi\!\left(n\right)$	$d\!\left(n\right)$	$\sigma\!\left(n\right)$
1	1	1	1	26	12	4	42
2	1	2	3	27	18	4	40
3	2	2	4	28	12	6	56
4	2	3	7	29	28	2	30
5	4	2	6	30	8	8	72
6	2	4	12	31	30	2	32
7	6	2	8	32	16	6	63
8	4	4	15	33	20	4	48
9	6	3	13	34	16	4	54
10	4	4	18	35	24	4	48
11	10	2	12	36	12	9	91
12	4	6	28	37	36	2	38
13	12	2	14	38	18	4	60
14	6	4	24	39	24	4	56
15	8	4	24	40	16	8	90
16	8	5	31	41	40	2	42
17	16	2	18	42	12	8	96
18	6	6	39	43	42	2	44
19	18	2	20	44	20	6	84
20	8	6	42	45	24	6	78
21	12	4	32	46	22	4	72
22	10	4	36	47	46	2	48
23	22	2	24	48	16	10	124
24	8	8	60	49	42	3	57
25	20	3	31	50	20	6	93

$n$	$p_{n}$	$p_{{n+20}}$	$p_{{n+40}}$	$p_{{n+60}}$	$p_{{n+80}}$
1	2	73	179	283	419
2	3	79	181	293	421
3	5	83	191	307	431
4	7	89	193	311	433
5	11	97	197	313	439
6	13	101	199	317	443
7	17	103	211	331	449
8	19	107	223	337	457
9	23	109	227	347	461
10	29	113	229	349	463
11	31	127	233	353	467
12	37	131	239	359	479
13	41	137	241	367	487
14	43	139	251	373	491
15	47	149	257	379	499
16	53	151	263	383	503
17	59	157	269	389	509
18	61	163	271	397	521
19	67	167	277	401	523
20	71	173	281	409	541

$n$	$\phi\!\left(n\right)$	$d\!\left(n\right)$	$\sigma\!\left(n\right)$	$n$	$\phi\!\left(n\right)$	$d\!\left(n\right)$	$\sigma\!\left(n\right)$
1	1	1	1	26	12	4	42
2	1	2	3	27	18	4	40
3	2	2	4	28	12	6	56
4	2	3	7	29	28	2	30
5	4	2	6	30	8	8	72
6	2	4	12	31	30	2	32
7	6	2	8	32	16	6	63
8	4	4	15	33	20	4	48
9	6	3	13	34	16	4	54
10	4	4	18	35	24	4	48
11	10	2	12	36	12	9	91
12	4	6	28	37	36	2	38
13	12	2	14	38	18	4	60
14	6	4	24	39	24	4	56
15	8	4	24	40	16	8	90
16	8	5	31	41	40	2	42
17	16	2	18	42	12	8	96
18	6	6	39	43	42	2	44
19	18	2	20	44	20	6	84
20	8	6	42	45	24	6	78
21	12	4	32	46	22	4	72
22	10	4	36	47	46	2	48
23	22	2	24	48	16	10	124
24	8	8	60	49	42	3	57
25	20	3	31	50	20	6	93

§ 27.2. Functions

Contents

§ 27.2(i). Definitions

§ 27.2(ii). Tables

$n$	$p_{n}$	$p_{{n+20}}$	$p_{{n+40}}$	$p_{{n+60}}$	$p_{{n+80}}$
1	2	73	179	283	419
2	3	79	181	293	421
3	5	83	191	307	431
4	7	89	193	311	433
5	11	97	197	313	439
6	13	101	199	317	443
7	17	103	211	331	449
8	19	107	223	337	457
9	23	109	227	347	461
10	29	113	229	349	463
11	31	127	233	353	467
12	37	131	239	359	479
13	41	137	241	367	487
14	43	139	251	373	491
15	47	149	257	379	499
16	53	151	263	383	503
17	59	157	269	389	509
18	61	163	271	397	521
19	67	167	277	401	523
20	71	173	281	409	541

$n$	$\phi\!\left(n\right)$	$d\!\left(n\right)$	$\sigma\!\left(n\right)$	$n$	$\phi\!\left(n\right)$	$d\!\left(n\right)$	$\sigma\!\left(n\right)$
1	1	1	1	26	12	4	42
2	1	2	3	27	18	4	40
3	2	2	4	28	12	6	56
4	2	3	7	29	28	2	30
5	4	2	6	30	8	8	72
6	2	4	12	31	30	2	32
7	6	2	8	32	16	6	63
8	4	4	15	33	20	4	48
9	6	3	13	34	16	4	54
10	4	4	18	35	24	4	48
11	10	2	12	36	12	9	91
12	4	6	28	37	36	2	38
13	12	2	14	38	18	4	60
14	6	4	24	39	24	4	56
15	8	4	24	40	16	8	90
16	8	5	31	41	40	2	42
17	16	2	18	42	12	8	96
18	6	6	39	43	42	2	44
19	18	2	20	44	20	6	84
20	8	6	42	45	24	6	78
21	12	4	32	46	22	4	72
22	10	4	36	47	46	2	48
23	22	2	24	48	16	10	124
24	8	8	60	49	42	3	57
25	20	3	31	50	20	6	93