§27.2 Functions

Referenced by:: §25.15(i), §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).
Defines:: $\mathop{d_{{k}}\/}\nolimits\!\left(n\right)$ : divisor function and $\mathop{\nu\/}\nolimits\!\left(n\right)$ : number of distinct primes dividing $n$
Keywords:: Euler–Fermat theorem, Euler’s totient, Jordan’s function, Liouville’s function, Mangoldt’s function, Möbius function, divisor function, fundamental theorem of arithmetic, multiplicative number theory, number-theoretic functions, number theory, prime numbers, prime number theorem, reduced residue system
Referenced by:: ¶ ‣ §26.18
Permalink:: http://dlmf.nist.gov/27.2.i

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}}^{{\mathop{\nu\/}\nolimits\!\left(n\right)}}p^{{a_{r}}}_{r},$

Symbols:: $\mathop{\nu\/}\nolimits\!\left(n\right)$ : number of distinct primes dividing $n$ , $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

where $p_{1},p_{2},\dots,p_{{\mathop{\nu\/}\nolimits\!\left(n\right)}}$ are the distinct prime factors of $n$ , each exponent $a_{r}$ is positive, and $\mathop{\nu\/}\nolimits\!\left(n\right)$ is the number of distinct primes dividing $n$ . ( $\mathop{\nu\/}\nolimits\!\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 $\mathop{\pi\/}\nolimits\!\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 $\mathop{\pi\/}\nolimits\!\left(x\right)=\sum _{{p\leq x}}1.$

Defines:: $\mathop{\pi\/}\nolimits\!\left(x\right)$ : number of primes not exceeding $x$
Symbols:: $p,p_{1},\ldots$ : prime numbers and $x$ : real number
Permalink:: http://dlmf.nist.gov/27.2.E2
Encodings:: TeX, pMML, png

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

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

Symbols:: $\mathop{\pi\/}\nolimits\!\left(x\right)$ : number of primes not exceeding $x$ , $\sim$ : asymptotic equality and $x$ : real number
Referenced by:: §25.16(i), §27.11
Permalink:: http://dlmf.nist.gov/27.2.E3
Encodings:: TeX, pMML, 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 (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\mathop{\mathrm{log}\,\/}\nolimits n$ as $n\to\infty$ :

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

Symbols:: $\sim$ : asymptotic equality, $n$ : positive integer and $p,p_{1},\ldots$ : prime numbers
Permalink:: http://dlmf.nist.gov/27.2.E4
Encodings:: TeX, pMML, 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:: $\left\lfloor 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

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

Defines:: $\mathop{\phi _{{k}}\/}\nolimits\!\left(n\right)$ : sum of powers of integers relatively prime to $n$
Symbols:: $k$ : positive integer, $m$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.2.E6
Encodings:: TeX, pMML, png

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

27.2.7 $\mathop{\phi\/}\nolimits\!\left(n\right)=\mathop{\phi _{{0}}\/}\nolimits\!\left(n\right).$

Symbols:: $\mathop{\phi _{{k}}\/}\nolimits\!\left(n\right)$ : sum of powers of integers relatively prime to $n$ and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.2.E7
Encodings:: TeX, pMML, png

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

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

27.2.8 $a^{{\mathop{\phi\/}\nolimits\!\left(n\right)}}\equiv 1\;\;(\mathop{{\rm mod}}n),$

Symbols:: $\mathop{\phi _{{k}}\/}\nolimits\!\left(n\right)$ : sum of powers of integers relatively prime to $n$ , $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

and if $\mathop{\phi\/}\nolimits\!\left(n\right)$ is the smallest positive integer $f$ such that $a^{f}\equiv 1\;\;(\mathop{{\rm mod}}n)$ , then $a$ is a primitive root mod $n$ . The $\mathop{\phi\/}\nolimits\!\left(n\right)$ numbers $a,a^{2},\dots,a^{{\mathop{\phi\/}\nolimits\!\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 $\mathop{d\/}\nolimits\!\left(n\right)=\sum _{{d\divides n}}1$

Symbols:: $\mathop{d_{{k}}\/}\nolimits\!\left(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

is the number of divisors of $n$ and is the divisor function. It is the special case $k=2$ of the function $\mathop{d_{{k}}\/}\nolimits\!\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 $\mathop{\sigma _{{\alpha}}\/}\nolimits\!\left(n\right)=\sum _{{d\divides n}}d^{\alpha},$

Defines:: $\mathop{\sigma _{{\alpha}}\/}\nolimits\!\left(n\right)$ : sum of powers of divisors of $n$
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

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

27.2.11 $\mathop{J_{{k}}\/}\nolimits\!\left(n\right)=\sum _{{((d_{1},\dots,d_{k}),n)=1}}1,$

Defines:: $\mathop{J_{{k}}\/}\nolimits\!\left(n\right)$ : Jordan’s function
Symbols:: $(a,b)$ : open interval, $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

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 $\mathop{J_{{1}}\/}\nolimits\!\left(n\right)=\mathop{\phi\/}\nolimits\!\left(n\right)$ .

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

27.2.12 $\mathop{\mu\/}\nolimits\!\left(n\right)=\begin{cases}1,&n=1,\\ (-1)^{{\mathop{\nu\/}\nolimits\!\left(n\right)}},&a_{1}=a_{2}=\dots=a_{{\mathop{\nu\/}\nolimits\!\left(n\right)}}=1,\\ 0,&\mbox{otherwise}.\end{cases}$

Defines:: $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function
Symbols:: $\mathop{\nu\/}\nolimits\!\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, pMML, png

This is the Möbius function.

27.2.13 $\mathop{\lambda\/}\nolimits\!\left(n\right)=\begin{cases}1,&n=1,\\ (-1)^{{a_{1}+\dots+a_{{\mathop{\nu\/}\nolimits\!\left(n\right)}}}},&n>1.\end{cases}$

Defines:: $\mathop{\lambda\/}\nolimits\!\left(n\right)$ : Liouville’s function
Symbols:: $\mathop{\nu\/}\nolimits\!\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, pMML, png

This is Liouville’s function.

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

Defines:: $\mathop{\Lambda\/}\nolimits\!\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, pMML, png

where $p^{a}$ is a prime power with $a\geq 1$ ; otherwise $\mathop{\Lambda\/}\nolimits\!\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.ii

Table 27.2.1 lists the first 100 prime numbers $p_{n}$ . Table 27.2.2 tabulates the Euler totient function $\mathop{\phi\/}\nolimits\!\left(n\right)$ , the divisor function $\mathop{d\/}\nolimits\!\left(n\right)$ ( $=\mathop{\sigma _{{0}}\/}\nolimits(n)$ ), and the sum of the divisors $\mathop{\sigma\/}\nolimits(n)$ ( $=\mathop{\sigma _{{1}}\/}\nolimits(n)$ ), for $n=1(1)52$ .

Table 27.2.1: Primes.

$n$	$p_{n}$	$p_{{n+10}}$	$p_{{n+20}}$	$p_{{n+30}}$	$p_{{n+40}}$	$p_{{n+50}}$	$p_{{n+60}}$	$p_{{n+70}}$	$p_{{n+80}}$	$p_{{n+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

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

Table 27.2.2: Functions related to division.

$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$	$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$	$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$	$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$
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

Symbols:: $\mathop{\phi _{{k}}\/}\nolimits\!\left(n\right)$ : sum of powers of integers relatively prime to $n$ , $\mathop{d_{{k}}\/}\nolimits\!\left(n\right)$ : divisor function, $\mathop{\sigma _{{\alpha}}\/}\nolimits\!\left(n\right)$ : sum of powers of divisors of $n$ 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+10}}$	$p_{{n+20}}$	$p_{{n+30}}$	$p_{{n+40}}$	$p_{{n+50}}$	$p_{{n+60}}$	$p_{{n+70}}$	$p_{{n+80}}$	$p_{{n+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

$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$	$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$	$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$	$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$
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

$n$	$p_{n}$	$p_{{n+10}}$	$p_{{n+20}}$	$p_{{n+30}}$	$p_{{n+40}}$	$p_{{n+50}}$	$p_{{n+60}}$	$p_{{n+70}}$	$p_{{n+80}}$	$p_{{n+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

$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$	$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$	$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$	$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$
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

§27.2 Functions

Contents

§27.2(i) Definitions

§27.2(ii) Tables

$n$	$p_{n}$	$p_{{n+10}}$	$p_{{n+20}}$	$p_{{n+30}}$	$p_{{n+40}}$	$p_{{n+50}}$	$p_{{n+60}}$	$p_{{n+70}}$	$p_{{n+80}}$	$p_{{n+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

$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$	$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$	$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$	$n$	$\mathop{\phi\/}\nolimits\!\left(n\right)$	$\mathop{d\/}\nolimits\!\left(n\right)$	$\mathop{\sigma\/}\nolimits\!\left(n\right)$
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